hdu4405Aeroplane chess 概率dp水题
DP 概率 水题
2023-09-11 14:20:43 时间
//从0到n有n+1个格子
//对于格子i,掷一次骰子的数为x。那么能够从位置i到位置i+x
//格子之间有连线,假设格子a和b有连线,那么从a到b不用掷骰子
//求从0到n的骰子掷的次数的期望
//dp[i] = 1/6*segma(dp[k]) + 1 (i<=k<=i+6)
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std ;
const int maxn = 100000 ;
double dp[maxn] ;
int line[maxn] ;
int main()
{
int n , m ;
while(scanf("%d%d" , &n ,&m) && n+m)
{
memset(line , -1 , sizeof(line)) ;
memset(dp , 0 ,sizeof(dp)) ;
int a , b ;
for(int i = 1;i <= m ;i++)
{
scanf("%d%d" ,&a , &b) ;
line[a] = b ;
}
for(int i = n-1 ;i >= 0 ;i--)
{
if(line[i] != -1){dp[i] = dp[line[i]] ;continue;}
for(int k = i + 1;k <= i+6 ;k++)
dp[i] += ((double)1/(double)6)*dp[k];
dp[i] += 1 ;
}
printf("%.4lf\n" , dp[0]) ;
}
return 0 ;
}
//对于格子i,掷一次骰子的数为x。那么能够从位置i到位置i+x
//格子之间有连线,假设格子a和b有连线,那么从a到b不用掷骰子
//求从0到n的骰子掷的次数的期望
//dp[i] = 1/6*segma(dp[k]) + 1 (i<=k<=i+6)
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std ;
const int maxn = 100000 ;
double dp[maxn] ;
int line[maxn] ;
int main()
{
int n , m ;
while(scanf("%d%d" , &n ,&m) && n+m)
{
memset(line , -1 , sizeof(line)) ;
memset(dp , 0 ,sizeof(dp)) ;
int a , b ;
for(int i = 1;i <= m ;i++)
{
scanf("%d%d" ,&a , &b) ;
line[a] = b ;
}
for(int i = n-1 ;i >= 0 ;i--)
{
if(line[i] != -1){dp[i] = dp[line[i]] ;continue;}
for(int k = i + 1;k <= i+6 ;k++)
dp[i] += ((double)1/(double)6)*dp[k];
dp[i] += 1 ;
}
printf("%.4lf\n" , dp[0]) ;
}
return 0 ;
}
相关文章
- ZOJ 1013 Great Equipment(DP)
- Leetcode2038. 如果相邻两个颜色均相同则删除当前颜色(medium, dp, greedy)
- POJ题目1947 Rebuilding Roads(树形dp)
- HDU 2845 Beans (DP)
- POJ 3934 Queue(DP)
- hdu 4975 最大流问题解决队伍和矩阵,利用矩阵dp优化
- hdu 3853 LOOPS (概率dp)
- Android度量单位说明(DIP,DP,PX,SP)
- poj 2096 Collecting Bugs 【概率DP】【逆向递推求期望】
- HDU 4050 wolf5x(动态规划-概率DP)
- POJ 3691 DNA repair 基于AC自己主动机DP
- HDU3853-LOOPS(概率DP求期望)
- PAT Maximum Subsequence Sum[最大子序列和,简单dp]
- 状态机DP例题
- 【强化学习】读书手札:动态规划(DP)&蒙特卡洛(MC)&时序差分(TD)区别