HDU4405（概率+期望DP）

 坚定替大佬打一波博客欣赏广告：blogs./kevinACMer/p/3724671.html

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=100005;
const int maxm=1005;
int vis[maxn];
double dp[maxn];
int n,m,a,b;
int main()
{while(scanf("%d%d",&n,&m)){if(!(n+m))break;memset(vis,-1,sizeof(vis));memset(dp,0,sizeof(dp));for(int i=0; i<m; i++){scanf("%d%d",&a,&b);vis[a]=b;//存储a的后继结点b}for(int i=n-1; i>=0; i--)if(vis[i]==-1){//dp[i]表示到达n处要投掷筛子次数的期望for(int j=1; j<=6; j++)dp[i]+=dp[i+j]/6;dp[i]+=1;//在i位置必然要投一次筛子}elsedp[i]=dp[vis[i]];printf("%.4lf\n",dp[0]);}return 0;
}