概率dp作业

概率dp特征：概率DP一般求的是实际结果，在DP过程中，当前状态是由所有子状态的概率共同转移而来，所以概率DP只是利用了DP的动态而没有规划（即只需转移无需决策）。-------qkoqhh

A - Collecting Bugs

题意：一个软件有s个子系统，会产生n种bug。某人一天发现一个bug，这个bug属于某种bug，发生在某个子系统中。

求找到所有的n种bug，且每个子系统都找到bug，这样所要的天数的期望。
需要注意的是：bug的数量是无穷大的，所以发现一个bug，出现在某个子系统的概率是1/s，属于某种类型的概率是1/n。

这题放在第一个，自然是入门题目，这里我在仔细温习下聚聚讲的状态和转移：

 f[i][j]:表示已经找到i种bug,分j类,找完剩下bug需要天数的期望。

 转移分4中情况，即分类和系统对于已知和未知的4种组合。

 相应概率也可以得出。注意4种状态对应的概率求和为1

 边界：f[n][s]= 求f[][]

 方程：dp[i][j]=(n-i)/n*(s-j)/s*dp[i+][j+]+(n-i)/n*j/s*dp[i+][j]+i/n*(s-j)/s*dp[i][j+]+i/n*j/s*dp[i][j]+

这里方程后面加1因为这是计算下一状态的期望，所以+1。

 #include <cstdio>

 #include <iostream>

 using namespace std;

 const int maxn = ;

 double dp[maxn][maxn];

 int main()

 {

     //freopen("in.txt", "r", stdin);

     int n, s;

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

         dp[n][s] = ;

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

             for(int j=s; j>=; j--){

                 if(i==n && j==s)continue;

                 dp[i][j] =  (dp[i+][j]*(n-i)*j+dp[i][j+]*i*(s-j)+dp[i+][j+]*(n-i)*(s-j)+n*s)/(n*s-i*j);

             }

         }

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

     }

     return ;

 }

B - Card Collector

题意：

集齐n张不同概率(p1,p2……pn)的卡片(一包最多一张)需要买多少包小吃，求期望。

Thinkging:

看数据范围n<=20，可以思考状态压缩(qkoqhh说的)。

这题状态也比较好定义 dp[s]: 已经收集到一些卡牌,状态压缩为s,要收集到所有卡牌的期望。

这题方程也比较好写

dp[s] =   Σ dp[s]*(q1+q2)           (s>>j & )==  //q1:没有卡片的概率  q2:抽出集合中存在的卡片

       +  Σ dp[s | <<j] * p[j]     (s>>j & )==

 #include <cstdio>

 #include <cstring>

 const int maxn = ;

 double P[maxn];

 double dp[<<maxn];

 int main(){

 //    freopen("in.txt", "r", stdin);

     int n;

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

         double p = ;

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

             scanf("%lf", &P[i]);

             p += P[i];

         }

         p =  - p;   //袋里没有卡片的概率

         dp[(<<n)-] = ;

         for(int s=(<<n)-; s>=; s--){

             double x = , y = ;

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

                 if((s>>j) & ){

                     x += P[j];

                 }else{

                     y += P[j]*dp[s | (<<j)];

                 }

                 dp[s] = y/(-x-p);

             }

         }

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

     }

     return ;

 }

C - Aeroplane chess

题意：在一个从0到n的格子上掷色子，从0点出发，掷了多少前进几步，同时有些格点直接相连，即若a，b相连，当落到a点时直接飞向b点。求走到n或超出n期望掷色子次数。

Thinking:

如果只是摇色子不飞行的话有如下转移：

dp[i]:从i走到n的期望步数

dp[i]= Σ /*dp[i+k]+1    k=..

加入飞行方式后两点的期望步数相等

这里可以用并查集维护飞行点的dp转移，注意并查集根部维护的是目标方向的结点

也可以用链式存储转移的关系，同样反向建立链接关系。

 #include <cstdio>

 #include <cstring>

 using namespace std;

 const int maxn = ;

 double dp[maxn];

 int f[maxn];

 int find(int x){

     return x==f[x]?x:f[x]=find(f[x]);

 }

 int main(){

 //    freopen("in.txt", "r", stdin);

     int n, m;

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

         memset(dp, , sizeof(dp));

         memset(f, , sizeof(f));

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

             f[i] = i;

         }

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

             int x, y;

             scanf("%d%d", &x,&y);

             f[find(x)] = find(y);

         }

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

             if(find(i) == i){  //这是不能跳跃的点

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

                     dp[i] += (dp[find(j)] + )/;

                 }

             }

         }

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

     }

 }

 #include <cstdio>

 #include <cstring>

 #include <vector>

 using namespace std;

 const int maxn = ;

 double dp[maxn];

 bool vis[maxn];

 vector<int> G[maxn];

 int main(){

 //    freopen("in.txt", "r", stdin);

     int n, m;

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

         memset(dp, , sizeof(dp));

         memset(vis, ,  sizeof(vis));

         for(int i=; i<=n; i++)G[i].clear();

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

             int x, y;

             scanf("%d%d", &x,&y);

             G[y].push_back(x);

             /*

              *反向建立链表，存储直接跳转的点对，方便下面逆着转移

             */

         }

         for(int i=; i<G[n].size(); i++){

             vis[G[n][i]] = true;

         }//与终点相连的点可直接跳转

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

             if(!vis[i]){  //这是不能跳跃的点

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

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

                 }

                 dp[i] += ;

                 vis[i] = true;

             }

             for(int j=; j<G[i].size(); j++){

                 dp[G[i][j]] = dp[i];

                 vis[G[i][j]] = true;

             }//可以直接跳转的点

         }

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

     }

     return ;

 }

E - Bag of mice

题意：一个袋子里有n个白老鼠，m个黑老鼠，王子和龙依次取，王子先取，先取到白老鼠的为胜者，其中龙取老鼠的时候，取出一只后，会有随机的一只老鼠跑出来，而且取老鼠的时候，每只老鼠取到的概率是一样的，跑出来的概率也是一样的，算王子赢的概率。

这里学习了kuangbin对这题的解析。看tutorial里用将问题分解为两个子问题(W,B)->(W,B-1)+(W-1,B-1)+(W,B-2)，这里可以设置一个标记回合的参数。

 #include <cstdio>

 #include <iostream>

 #include <cstdlib>

 #include <cmath>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 #define LL long long

 const int maxn = ;

 double dp[maxn][maxn];

 //dp[i][j]:到王妃抓时还剩 i只白鼠j只黑鼠时王妃胜的概率

 int main(){

     //freopen("in.txt", "r", stdin);

     memset(dp, , sizeof());

     int w,b;

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

     for(int i=; i<=b; i++)dp[][i]=;

     // 没有白鼠时胜率为0

     for(int i=; i<=w; i++)dp[i][]=;

     //没有黑鼠时 胜率为1

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

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

             dp[i][j] += (double)i/(i+j);//王妃抓到一只白鼠

             if(j>=){

                 dp[i][j] += ((double)j/(i+j)) * ((double)(j-)/(i+j-)) * ((double)(j-)/(i+j-)) * dp[i][j-];

             }//王妃抓到黑，龙抓到一个黑，放了一个黑

             if(j>=){

                 dp[i][j] += ((double)j/(i+j)) * ((double)(j-)/(i+j-)) * ((double)i/(i+j-)) * dp[i-][j-];

             }//王妃抓到黑，龙抓到黑，放了一个白

         }

     }

     printf("%.9lf\n", dp[w][b]);

     return ;

 }

 double dfs(int w, int b, int flag){

     if(w == ) return flag;  //flag=1:此轮龙抓,龙胜返回1; 代表两人都没抓到白鼠，龙胜

     if(b == ) return ;

     double &memo = dp[w][b][flag];

     if(memo > -0.5) return memo;

     double ans = ;

     if(flag == ){

         ans += (double)w/(w + b);   //王妃抓白鼠胜

         ans += ((double)b/(w + b)) * ( - dfs(w, b-, ));

         //王妃抓黑鼠，下一轮龙抓失败的概率(dfs()返回成功的概率) 即王妃胜

     }else{

         ans += (double)w/(w + b);   //龙抓白鼠胜的概率

         ans += ((double)b/(w + b)) * ((double)w/(w+b-)) * ( - dfs(w-, b-, ));

         // 龙抓一个黑鼠放一个白鼠胜的概率

         if(b > ) { //龙抓一个黑鼠 放一个黑鼠胜的概率

             ans += ((double)b/(w + b)) * ((double)(b-)/(w + b-)) * ( - dfs(w, b-, ));

         }

     }

     return memo = ans;

 }

 dp[i][j][]=dp[i][j][] = -

巴特西

概率dp作业

最新文章

热门文章