概率dp 期望逆推

题目大意：

从起点0点开始到达点n，通过每次掷色子前进，可扔出1,2,3,4,5,6这6种情况，扔到几前进几，当然对应飞行通道可以通过x直达一点y，x<y，计算到达n点或超过n

点要扔色子的次数的数学期望

从某一点 i 扔完色子可到达 i+1,i+2,i+3,i+4,i+5,i+6这6个点，令dp[i]为到达末尾的数学期望

那么到达之后6个点的数学期望是一样的，那么dp[i]=dp[i+1]*1/6.0+dp[i+2]*1/6.0+dp[i+3]*1/6.0+dp[i+4]*1/6.0+dp[i+5]*1/6.0+dp[i+6]*1/6.0+1

碰到可以直接飞的进行一个if判断，直接将dp值赋予即可，不执行上述的dp操作过程

 #include<cstdio>

 #include<algorithm>

 #include<math.h>

 #include<string.h>

 using namespace std;

 const int maxn=1e5+;

 int match[maxn];

 double dp[maxn];

 void init()

 {

     memset(dp,,sizeof(dp));

     memset(match,,sizeof(match));

 }

 int main()

 {

     int n,m;

     while(scanf("%d%d",&n,&m)!=EOF){

         if(n==&&m==) break;

         init();

         for(int i=;i<=m;i++){

             int a,b;

             scanf("%d%d",&a,&b);

             match[a]=b;

         }

         for(int i=n-;i>=;i--){

             if(match[i]) dp[i]=dp[match[i]];

             else{

                 for(int j=;j<=;j++){

                     dp[i]+=dp[j+i]/6.0;

                 }

                 dp[i]+=;

             }

         }

         printf("%.4f\n",dp[]);

     }

     return ;

 }

巴特西

概率dp 期望逆推

最新文章

热门文章

巴特西

概率dp 期望 逆推

最新文章

热门文章

概率dp 期望逆推