概率DP小结-白红宇

概率DP小结

阅读量：6246 次

发布时间：2019-06-22

本文共 9126 字，大约阅读时间需要 30 分钟。

hdu 4089 Activation

去年北京现场赛的一道题，当时没做过概率DP, 用DP怎么搞都不对，最近才把概率DP学了学终于把这道题A了。

有n个人排队激活游戏账号，每次会有四种情况发生。

1.激活失败：队列保持不变，发生的概率为p1

2.连接失败：队首重新排到队尾，队列长度不变，发生的概率为p2

3.激活成功：队首移出队列，后面的元素都往前移一位，队列长度减1，发生的概率为p3

4.服务器崩溃：不再提供服务。

刚开始有n个人在排队，Tomato在第m个位置，问最后服务器崩溃的时候Tomato在队列的前k个位置发生的概率。

用dp[i][j]记录队列里面有i个人，Tomato在第j个位置的概率，那最后dp[n][m]即为所求。

dp[i][1]=p1*dp[i][1]+dp[i][i]*p2+p4

dp[i][j]=p1*dp[i][j] + dp[i][j-1]*p2+dp[i-1][j-1]*p3+p4; (j<=k)

dp[i][j]=p1*dp[i][j] + dp[i][j-1]*p2+dp[i-1][j-1]*p3;(j>k)

令

p21=p2/(1-p1);

p31=p3/(1-p1);

p41=p4/(1-p1);

dp[i][1]=p21*dp[i][1]+p41;

dp[i][j]=p21*dp[i][j-1]+dp[i-1][j-1]*p31+p41;(j<=k)

dp[i][j]=p21*dp[i][j-1]+dp[i-1][j-1]*p31;(j>k)

因为dp[i-1][j-1]在递推的时候可以解决

所以最后就转换成：

a[n]=An*a[n-1]+Cn;

a[n-1]=An-1 * a[n-2]+Cn-1;

...

a[2]=A2*a[1]+C2;

a[1]=A1*a[n]+C1;

通过迭代可以首先求出a[n],之后就可以求出所有的。

View Code

1 # include
      
        2 # include
       
         3 # include
        
          4 # include
         
           5 # define N 2005 6 # define eps 1e-10 7 double dp[N][N],c[N]; 8 int main() 9 {10     int i,j,n,m,K;11     double p1,p2,p3,p4;12     double p21,p31,p41;13     double ans,sum;14     while(scanf("%d%d%d",&n,&m,&K)!=EOF)15     {16         scanf("%lf%lf%lf%lf",&p1,&p2,&p3,&p4);17         if(fabs(p4)
          
           =2;j--)25             {26                 c[j]=p31*dp[i-1][j-1];27                 if(j<=K) c[j]+=p41;28             }29             c[1]=p41;30             ans=1;//系数31             sum=0;//常数和32             for(j=i;j>=1;j--)33             {34                 sum+=ans*c[j];35                 ans*=p21;36             }37             dp[i][i]=sum/(1-ans);38             dp[i][0]=dp[i][i];39             for(j=1;j

hdu 4035 Maze

有n个房间，有n-1条路连接，刚开始一个人在第1个房间里，当在一个房间的时候会有三种情况发生：

1.被kill，然后重新在第1个房间复活，概率为K[i]

2.直接离开这n个房间,概率为E[i]

3.继续访问相邻的房间，如果与该房间相邻的房间数为m，到每一个房间的概率相等，均为(1-K[i]-E[i])/m;

问最后这人离开时所走步数的期望值。

假设用dp[i]表示从第i个房间到最后离开所需要走的步数的期望值。

那么最后dp[1]即为所求。

可以把n个房间看成一个以1为根的树。

若i为叶子节点： dp[i]=K[i]*dp[1]+E[i]*0+(1-K[i]-E[i])*(dp[F[i]]+1); F[i]表示 i 的父亲节点

不是叶子节点： dp[i]=K[i]*dp[1]+E[i]*0+(1-K[i]-E[i])/m * ( sum(dp[j]+1) + dp[F[i]]+1 ); j表示 i 的子节点，m表示与 i 相连的节点数

现在我们把dp[i]转化成dp[i]=A[i]*dp[1] + B[i] *dp[F[i]] + C[i]的形式，

把dp[j]=A[j]*dp[1] + B[j] * dp[F[j]] + C[j]代入上式，然后进行比较，可以得出

tt=(1-K[i]-E[i])/m;

A[i]=(K[i]+tt*sum(A[j])) / (1-tt*sum(B[j]));

B[i]=tt / (1-tt*sum(B[j]));

C[i]=(1-K[i]-E[i]+tt*sum(C[j]))/(1-tt*sum(B[j]));

最后dp[1]=A[1]*dp[1]+B[1]*0+C[1];

dp[1]=C[1]/(1-A[1]);

View Code

1 # include
      
        2 # include
       
         3 # include
        
          4 # include
         
           5 # define N 10005 6 # define eps 1e-10 7 struct Edge{ 8     int from,to,next; 9 }edge[2*N];10 int tol,head[N];11 double K[N],E[N];12 double A[N],B[N],C[N];13 void add(int a,int b)14 {15     edge[tol].from=a;edge[tol].to=b;edge[tol].next=head[a];head[a]=tol++;16 }17 void dfs(int u,int father)18 {19     int j,v,cnt=0;20     double sumA,sumB,sumC,tt;21     A[u]=B[u]=C[u]=0;22     sumA=sumB=sumC=0.0;23     for(j=head[u];j!=-1;j=edge[j].next)24     {25         v=edge[j].to;26         if(v==father) continue;27         cnt++;28         dfs(v,u);29         sumA+=A[v];30         sumB+=B[v];31         sumC+=C[v];32     }33     if(cnt==0) //叶子节点34     {35         A[u]=K[u];36         B[u]=1-K[u]-E[u];37         C[u]=1-K[u]-E[u];38         return ;39     }40     if(u!=1) cnt++;41     tt=(1-K[u]-E[u])/cnt;42     A[u]=(K[u]+tt*sumA) / (1-tt*sumB);43     B[u]=tt / (1-tt*sumB);44     C[u]=(1-K[u]-E[u]+tt*sumC)/(1-tt*sumB);45 }46 int main()47 {48     int i,n,ncase,t;49     int a,b;50     scanf("%d",&ncase);51     for(t=1;t<=ncase;t++)52     {53         scanf("%d",&n);54         tol=0;55         memset(head,-1,sizeof(head));56         for(i=2;i<=n;i++)57         {58             scanf("%d%d",&a,&b);59             add(a,b);60             add(b,a);61         }62         for(i=1;i<=n;i++)63         {64             scanf("%lf%lf",&K[i],&E[i]);65             K[i]/=100;66             E[i]/=100;67         }68         dfs(1,0);69         printf("Case %d: ",t);70         if(fabs(1-A[1])

poj 2151 Check the difficulty of problems

T个人做m道题，现已知每个人做出来每道题目的概率，问最后每个人都至少做出一道题，并且做题数最多的人所做的题数不小于n的概率。

首先可以求出每个人都至少做出一道题的概率，再求出每个人做的题目数都大于等于1并且小于n的概率。

我们用dp[i][j][k]来表示第i个人，前j道题目做出来k道的概率。

这样上面两个概率就很容易求了。

View Code

1 # include
      
        2 # include
       
         3 # include
        
          4 # define Pr 32 5 # define Te 1005 6 double Probable[Te][Pr]; 7 double dp[Te][Pr][Pr]; 8 int main() 9 {10     int i,j,k,M,T,N;11     double ans,ans1,sum;12     while(scanf("%d%d%d",&M,&T,&N)!=EOF)13     {14         if(M==0 && N==0 && T==0) break;15         for(i=1;i<=T;i++)16             for(j=1;j<=M;j++)17                 scanf("%lf",&Probable[i][j]);18         memset(dp,0,sizeof(dp));19         for(i=1;i<=T;i++)//dp[i][j][k],第i个队的前j道题目做出来k道20         {21             dp[i][0][0]=1;22             for(j=1;j<=M;j++)23                 for(k=0;k<=j;k++)24                 {25                     if(k==0) dp[i][j][0]=dp[i][j-1][0]*(1-Probable[i][j]);26                     else dp[i][j][k]=dp[i][j-1][k-1]*Probable[i][j]+dp[i][j-1][k]*(1-Probable[i][j]);27                 }28         }29         ans=1;30         for(i=1;i<=T;i++)31         {32             sum=0;33             for(j=1;j<=M;j++)34                 sum+=dp[i][M][j];35             ans*=sum;36         }37         ans1=1;38         for(i=1;i<=T;i++)39         {40             sum=0;41             for(j=1;j

poj 3071 Football

有2^n个球队，然后两两进行淘汰赛，知道最后剩下一支队伍，也就是冠军。

现已知任何两支球队碰面时每支球队获胜的概率，问最后哪一支球队夺冠的希望最大。

很明显是一个概率dp的问题，需要注意的是每一轮淘汰赛，一个球队有可能碰见哪些球队。

这个可以先预处理出来。

View Code

1 # include
      
        2 # include
       
         3 # include
        
          4 double dp[8][130],map[130][130]; 5 int a[10]; 6 struct node{ 7     int up,down; 8 }s[8][130]; 9 int find(int i,int k)10 {11     int ans;12     ans=(i-1)/a[k-1]+1;13     if(ans%2) return ans+1;14     return ans-1;15 }16 int main()17 {18     int i,j,k,n,index;19     int ans;20     double Max;21     a[0]=1;22     for(i=1;i<=7;i++)23         a[i]=a[i-1]*2;24     for(i=1;i<=7;i++)25     {26         ans=0;27         k=0;28         while(ans<128)29         {30             s[i][++k].up=ans+1;31             s[i][k].down=s[i][k].up+a[i-1]-1;32             ans=s[i][k].down;///第i轮淘汰赛在第k阵营的队伍的上界与下界33         }34     }35     while(scanf("%d",&n)!=EOF && n!=-1)36     {37         for(i=1;i<=a[n];i++)38             for(j=1;j<=a[n];j++)39                 scanf("%lf",&map[i][j]);40         memset(dp,0,sizeof(dp));41         for(i=1;i<=a[n];i++)42             dp[0][i]=1;43         for(k=1;k<=n;k++)44         {45             for(i=1;i<=a[n];i++)46             {47                 ans=find(i,k);//找第k轮与第i个队伍所在的阵营对立的阵营48                 for(j=s[k][ans].up;j<=s[k][ans].down;j++)49                     dp[k][i]+=dp[k-1][i]*dp[k-1][j]*map[i][j];50             }51         }52         Max=dp[n][1];53         index=1;54         for(i=2;i<=a[n];i++)55             if(dp[n][i]>Max) {Max=dp[n][i];index=i;}56         printf("%d\n",index);57     }58     return 0;59 }

zoj 3551 Bloodsucker

刚开始有n-1个人，1个吸血鬼，然后以后每天这n个中的其中两个会相遇，如果一个是吸血鬼，一个是人，那这个人有一定的概率p变成吸血鬼。

问着n个最后都变成吸血鬼所需天数的期望值。

用dp[i]来表示有i个吸血鬼时的期望值,dp[n]=0;

dp[1]即为所求。

dp[i]=p1*dp[i]+p2*dp[i+1]+1,(p1+p2=1)

View Code

1 # include
      
        2 # include
       
         3 # include
        
          4 # define N 100005 5 double dp[N]; 6 int main() 7 { 8     int j,ncase,n; 9     double p,ans1,ans2,p2;10     scanf("%d",&ncase);11     while(ncase--)12     {13         scanf("%d%lf",&n,&p);14         dp[n]=0; 15         //dp[i],表示吸血鬼数量为i时，到目标还需要多少天16         //dp[i]=p1*dp[i]+p2*dp[i+1]+1,(p1+p2=1)17         for(j=n-1;j>=1;j--)18         {19             ans1=j;20             ans1*=n-j;21             ans2=n;22             ans2*=n-1;23             ans2/=2;24             p2=ans1/ans2 * p;25             dp[j]=dp[j+1]+1.0/p2;26         }27         printf("%.3lf\n",dp[1]);28     }29     return 0;30 }

codeforces 148 D Bag of mice

公主和龙轮流从bags里面取老鼠，谁先去到白鼠谁赢。

但是龙的身体比较庞大，会吓着老鼠，每次当他取老鼠时，都会从袋子里面再跳出来一只老鼠。

求最后公主赢的概率多大。

直接DP就可以了。

View Code

1 # include
      
        2 # include
       
         3 # include
        
          4 # define N 1005 5 double dp[N][N][2]; 6 int w,b; 7 int main() 8 { 9     int i,j;10     while(scanf("%d%d",&w,&b)!=EOF)11     {12         memset(dp,0,sizeof(dp));13         //dp[i][j][0],表示现在bags里面有i个白鼠，j个黑鼠，然后现在轮到公主了14         //dp[i][j][1],表示现在bags里面有i个白鼠，j个黑鼠，然后现在轮到dragon了15         for(i=0;i<=w;i++)16             for(j=0;j<=b;j++)17             {18                 if(i!=0) dp[i][j][0]=1.0*i/(i+j); //轮到公主的时候公主直接取一个白鼠19                 if(j!=0) dp[i][j][0]+=1.0*j/(i+j)*dp[i][j-1][1];//公主取的是一个黑鼠20                 if(i>=1 && j>=1) dp[i][j][1]=1.0*j/(i+j)*(1.0*i/(i+j-1))*dp[i-1][j-1][0];//dragon取黑鼠，然后吓跑一个白鼠21                 if(j>=2) dp[i][j][1]+=1.0*j/(i+j)*(1.0*(j-1)/(i+j-1))*dp[i][j-2][0];//dragon取黑鼠，然后又吓跑一个黑鼠22             }23             printf("%.9lf\n",dp[w][b][0]);24     }25     return 0;26 }