概率dp特征： 概率DP一般求的是实际结果，在DP过程中，当前状态是由所有子状态的概率共同转移而来，所以概率DP只是利用了DP的动态而没有规划（即只需转移无需决策）。-------qkoqhh
A - Collecting Bugs
题意：一个软件有s个子系统，会产生n种bug。某人一天发现一个bug，这个bug属于某种bug，发生在某个子系统中。
求找到所有的n种bug，且每个子系统都找到bug，这样所要的天数的期望。
需要注意的是：bug的数量是无穷大的，所以发现一个bug，出现在某个子系统的概率是1/s，属于某种类型的概率是1/n。
这题放在第一个，自然是入门题目，这里我在仔细温习下聚聚讲的状态和转移：
1 f[i][j]:表示已经找到i种bug,分j类,找完剩下bug需要天数的期望。 2 转移分4中情况，即分类和系统对于已知和未知的4种组合。 3 相应概率也可以得出。注意4种状态对应的概率求和为1 4 边界：f[n][s]=0 求f[0][0] 5 方程：dp[i][j]=(n-i)/n*(s-j)/s*dp[i+1][j+1]+(n-i)/n*j/s*dp[i+1][j]+i/n*(s-j)/s*dp[i][j+1]+i/n*j/s*dp[i][j]+1
这里方程后面加1因为这是计算下一状态的期望，所以+1。
1 #include <cstdio> 2 #include <iostream> 3 using namespace std; 4 const int maxn = 1010; 5 double dp[maxn][maxn]; 6 int main() 7 { 8 //freopen("in.txt", "r", stdin); 9 int n, s; 10 while(scanf("%d%d", &n, &s) != EOF){ 11 dp[n][s] = 0; 12 for(int i=n; i>=0; i--){ 13 for(int j=s; j>=0; j--){ 14 if(i==n && j==s)continue; 15 dp[i][j] = (dp[i+1][j]*(n-i)*j+dp[i][j+1]*i*(s-j)+dp[i+1][j+1]*(n-i)*(s-j)+n*s)/(n*s-i*j); 16 } 17 } 18 printf("%.4f ", dp[0][0]); 19 } 20 return 0; 21 }
B - Card Collector
题意：
集齐n张不同概率(p1,p2……pn)的卡片(一包最多一张)需要买多少包小吃，求期望。
Thinkging:
看数据范围n<=20，可以思考状态压缩(qkoqhh说的)。
这题状态也比较好定义 dp[s]: 已经收集到一些卡牌,状态压缩为s,要收集到所有卡牌的期望。
这题方程也比较好写
dp[s] = Σ dp[s]*(q1+q2) (s>>j & 1)==1 //q1:没有卡片的概率 q2:抽出集合中存在的卡片 + Σ dp[s | 1<<j] * p[j] (s>>j & 1)==0
1 #include <cstdio> 2 #include <cstring> 3 const int maxn = 21; 4 double P[maxn]; 5 double dp[1<<maxn]; 6 int main(){ 7 // freopen("in.txt", "r", stdin); 8 int n; 9 while(scanf("%d", &n) != EOF){ 10 double p = 0; 11 for(int i=0; i<n; i++){ 12 scanf("%lf", &P[i]); 13 p += P[i]; 14 } 15 p = 1 - p; //袋里没有卡片的概率 16 dp[(1<<n)-1] = 0; 17 for(int s=(1<<n)-2; s>=0; s--){ 18 double x = 0, y = 1; 19 for(int j=0; j<n; j++){ 20 if((s>>j) & 1){ 21 x += P[j]; 22 }else{ 23 y += P[j]*dp[s | (1<<j)]; 24 } 25 dp[s] = y/(1-x-p); 26 } 27 } 28 printf("%.5f ", dp[0]); 29 } 30 return 0; 31 }
C - Aeroplane chess
题意：在一个从0到n的格子上掷色子，从0点出发，掷了多少前进几步，同时有些格点直接相连，即若a，b相连，当落到a点时直接飞向b点。求走到n或超出n期望掷色子次数。
Thinking:
如果只是摇色子不飞行的话有如下转移：
dp[i]:从i走到n的期望步数 dp[i]= Σ 1/6*dp[i+k]+1 k=1..6
加入飞行方式后两点的期望步数相等
这里可以用并查集维护飞行点的dp转移，注意并查集根部维护的是目标方向的结点
也可以用链式存储转移的关系，同样反向建立链接关系。
1 #include <cstdio> 2 #include <cstring> 3 using namespace std; 4 const int maxn = 100010; 5 double dp[maxn]; 6 int f[maxn]; 7 int find(int x){ 8 return x==f[x]?x:f[x]=find(f[x]); 9 } 10 int main(){ 11 // freopen("in.txt", "r", stdin); 12 int n, m; 13 while( scanf("%d%d", &n, &m) != EOF && n){ 14 memset(dp, 0, sizeof(dp)); 15 memset(f, 0, sizeof(f)); 16 for(int i=1; i<=n+6; i++){ 17 f[i] = i; 18 } 19 for(int i=0; i<m; i++){ 20 int x, y; 21 scanf("%d%d", &x,&y); 22 f[find(x)] = find(y); 23 } 24 for(int i=n-1; i>=0; i--){ 25 if(find(i) == i){ //这是不能跳跃的点 26 for(int j=i+1; j<=i+6; j++){ 27 dp[i] += (dp[find(j)] + 1)/6; 28 } 29 } 30 } 31 printf("%.4f ", dp[0]); 32 } 33 }
1 #include <cstdio> 2 #include <cstring> 3 #include <vector> 4 using namespace std; 5 const int maxn = 100010; 6 double dp[maxn]; 7 bool vis[maxn]; 8 vector<int> G[maxn]; 9 int main(){ 10 // freopen("in.txt", "r", stdin); 11 int n, m; 12 while( scanf("%d%d", &n, &m) != EOF && (n+m)){ 13 memset(dp, 0, sizeof(dp)); 14 memset(vis, 0, sizeof(vis)); 15 for(int i=0; i<=n; i++)G[i].clear(); 16 for(int i=0; i<m; i++){ 17 int x, y; 18 scanf("%d%d", &x,&y); 19 G[y].push_back(x); 20 /* 21 *反向建立链表，存储直接跳转的点对，方便下面逆着转移 22 */ 23 } 24 for(int i=0; i<G[n].size(); i++){ 25 vis[G[n][i]] = true; 26 }//与终点相连的点可直接跳转 27 for(int i=n-1; i>=0; i--){ 28 if(!vis[i]){ //这是不能跳跃的点 29 for(int j=i+1; j<=i+6; j++){ 30 dp[i] += dp[j]/6; 31 } 32 dp[i] += 1; 33 vis[i] = true; 34 } 35 for(int j=0; j<G[i].size(); j++){ 36 dp[G[i][j]] = dp[i]; 37 vis[G[i][j]] = true; 38 }//可以直接跳转的点 39 } 40 printf("%.4f ", dp[0]); 41 } 42 return 0; 43 }
E - Bag of mice
题意：一个袋子里有n个白老鼠，m个黑老鼠，王子和龙依次取，王子先取，先取到白老鼠的为胜者，其中龙取老鼠的时候，取出一只后，会有随机的一只老鼠跑出来，而且取老鼠的时候，每只老鼠取到的概率是一样的，跑出来的概率也是一样的，算王子赢的概率。
这里学习了kuangbin对这题的解析。看tutorial里用将问题分解为两个子问题(W,B)->(W,B-1)+(W-1,B-1)+(W,B-2)，这里可以设置一个标记回合的参数。
1 #include <cstdio> 2 #include <iostream> 3 #include <cstdlib> 4 #include <cmath> 5 #include <cstring> 6 #include <algorithm> 7 using namespace std; 8 #define LL long long 9 10 const int maxn = 1010; 11 double dp[maxn][maxn]; 12 //dp[i][j]:到王妃抓时还剩 i只白鼠j只黑鼠时王妃胜的概率 13 int main(){ 14 //freopen("in.txt", "r", stdin); 15 memset(dp, 0, sizeof(0)); 16 int w,b; 17 scanf("%d%d", &w, &b); 18 for(int i=0; i<=b; i++)dp[0][i]=0; 19 // 没有白鼠时胜率为0 20 for(int i=1; i<=w; i++)dp[i][0]=1; 21 //没有黑鼠时 胜率为1 22 for(int i=1; i<=w; i++){ 23 for(int j=1; j<=b; j++){ 24 dp[i][j] += (double)i/(i+j);//王妃抓到一只白鼠 25 if(j>=3){ 26 dp[i][j] += ((double)j/(i+j)) * ((double)(j-1)/(i+j-1)) * ((double)(j-2)/(i+j-2)) * dp[i][j-3]; 27 }//王妃抓到黑，龙抓到一个黑，放了一个黑 28 if(j>=2){ 29 dp[i][j] += ((double)j/(i+j)) * ((double)(j-1)/(i+j-1)) * ((double)i/(i+j-2)) * dp[i-1][j-2]; 30 }//王妃抓到黑，龙抓到黑，放了一个白 31 } 32 } 33 printf("%.9lf ", dp[w][b]); 34 return 0; 35 }
1 double dfs(int w, int b, int flag){ 2 if(w == 0) return flag; //flag=1:此轮龙抓,龙胜返回1; 代表两人都没抓到白鼠，龙胜 3 if(b == 0) return 1; 4 double &memo = dp[w][b][flag]; 5 if(memo > -0.5) return memo; 6 double ans = 0; 7 if(flag == 0){ 8 ans += (double)w/(w + b); //王妃抓白鼠胜 9 ans += ((double)b/(w + b)) * (1 - dfs(w, b-1, 1)); 10 //王妃抓黑鼠，下一轮龙抓失败的概率(dfs()返回成功的概率) 即王妃胜 11 }else{ 12 ans += (double)w/(w + b); //龙抓白鼠胜的概率 13 ans += ((double)b/(w + b)) * ((double)w/(w+b-1)) * (1 - dfs(w-1, b-1, 0)); 14 // 龙抓一个黑鼠放一个白鼠胜的概率 15 if(b > 1) { //龙抓一个黑鼠 放一个黑鼠胜的概率 16 ans += ((double)b/(w + b)) * ((double)(b-1)/(w + b-1)) * (1 - dfs(w, b-2, 0)); 17 } 18 } 19 return memo = ans; 20 } 21 dp[i][j][0]=dp[i][j][1] = -1