概率DP主要用于求解期望、概率等題目。

轉移方程有時候比較靈活。

一般求概率是正推，求期望是逆推。通過題目可以體會到這點。

?

首先先推薦幾篇參考的論文：

《信息學競賽中概率問題求解初探》

《淺析競賽中一類數(shù)學期望問題的解決方法》

《有關概率和期望問題的研究 》

?

1、POJ 3744?

Scout YYF I 此題是一個用矩陣優(yōu)化的求概率的題目。 主要思想是分段，根據(jù)轉移方程用矩陣求解。 題解見 here POJ 3744 /* POJ 3744C++ 0ms 184K */ #include<stdio.h> #include<string.h> #include<algorithm> #include<iostream> #include<math.h> using namespace std;struct Matrix {double mat[2][2]; }; Matrix mul(Matrix a,Matrix b) {Matrix ret;for(int i=0;i<2;i++)for(int j=0;j<2;j++){ret.mat[i][j]=0;for(int k=0;k<2;k++)ret.mat[i][j]+=a.mat[i][k]*b.mat[k][j];}return ret; } Matrix pow_M(Matrix a,int n) {Matrix ret;memset(ret.mat,0,sizeof(ret.mat));for(int i=0;i<2;i++)ret.mat[i][i]=1;Matrix temp=a;while(n){if(n&1)ret=mul(ret,temp);temp=mul(temp,temp);n>>=1;}return ret; }int x[30]; int main() {int n;double p;while(scanf("%d%lf",&n,&p)!=EOF)//POJ上G++要改為cin輸入 {for(int i=0;i<n;i++)scanf("%d",&x[i]);sort(x,x+n);double ans=1;Matrix tt;tt.mat[0][0]=p;tt.mat[0][1]=1-p;tt.mat[1][0]=1;tt.mat[1][1]=0;Matrix temp;temp=pow_M(tt,x[0]-1);ans*=(1-temp.mat[0][0]);for(int i=1;i<n;i++){if(x[i]==x[i-1])continue;temp=pow_M(tt,x[i]-x[i-1]-1);ans*=(1-temp.mat[0][0]);}printf("%.7lf\n",ans);//POJ上G++要改為%.7f }return 0; }

?

?2、POJ 2096?Collecting Bugs

dp求期望，概率dp入門題。很簡單，題解見here

POJ 2096 /* POJ 2096 概率DP writed by kuangbindp求期望 逆著遞推求解 題意：（題意看題目確實比較難道，n和s都要找半天才能找到）一個軟件有s個子系統(tǒng)，會產(chǎn)生n種bug某人一天發(fā)現(xiàn)一個bug,這個bug屬于一個子系統(tǒng)，屬于一個分類每個bug屬于某個子系統(tǒng)的概率是1/s,屬于某種分類的概率是1/n問發(fā)現(xiàn)n種bug,每個子系統(tǒng)都發(fā)現(xiàn)bug的天數(shù)的期望。求解：dp[i][j]表示已經(jīng)找到i種bug,j個系統(tǒng)的bug，達到目標狀態(tài)的天數(shù)的期望dp[n][s]=0;要求的答案是dp[0][0];dp[i][j]可以轉化成以下四種狀態(tài):dp[i][j],發(fā)現(xiàn)一個bug屬于已經(jīng)有的i個分類和j個系統(tǒng)。概率為(i/n)*(j/s);dp[i][j+1],發(fā)現(xiàn)一個bug屬于已有的分類，不屬于已有的系統(tǒng).概率為 (i/n)*(1-j/s);dp[i+1][j],發(fā)現(xiàn)一個bug屬于已有的系統(tǒng)，不屬于已有的分類,概率為 (1-i/n)*(j/s);dp[i+1][j+1],發(fā)現(xiàn)一個bug不屬于已有的系統(tǒng)，不屬于已有的分類,概率為 (1-i/n)*(1-j/s);整理便得到轉移方程 */ #include<stdio.h> #include<iostream> #include<algorithm> #include<string.h> using namespace std; const int MAXN=1010; double dp[MAXN][MAXN];int main() {int n,s;while(scanf("%d%d",&n,&s)!=EOF){dp[n][s]=0;for(int i=n;i>=0;i--)for(int j=s;j>=0;j--){if(i==n&&j==s)continue;dp[i][j]=(i*(s-j)*dp[i][j+1]+(n-i)*j*dp[i+1][j]+(n-i)*(s-j)*dp[i+1][j+1]+n*s)/(n*s-i*j);}printf("%.4lf\n",dp[0][0]);//POJ上G++要改成%.4f }return 0; }

?

?3、ZOJ 3329? One Person Game

此題的遞推方程稍微復雜點，需要轉化后求解系數(shù)。

題意：有三個骰子，分別有k1,k2,k3個面。
每次擲骰子，如果三個面分別為a,b,c則分數(shù)置0，否則加上三個骰子的分數(shù)之和。
當分數(shù)大于n時結束。求游戲的期望步數(shù)。初始分數(shù)為0

題解見here

?

ZOJ 3329 /* ZOJ 3329 題意：有三個骰子，分別有k1,k2,k3個面。 每次擲骰子，如果三個面分別為a,b,c則分數(shù)置0，否則加上三個骰子的分數(shù)之和。 當分數(shù)大于n時結束。求游戲的期望步數(shù)。初始分數(shù)為0設dp[i]表示達到i分時到達目標狀態(tài)的期望，pk為投擲k分的概率，p0為回到0的概率 則dp[i]=∑(pk*dp[i+k])+dp[0]*p0+1; 都和dp[0]有關系，而且dp[0]就是我們所求，為常數(shù) 設dp[i]=A[i]*dp[0]+B[i]; 代入上述方程右邊得到： dp[i]=∑(pk*A[i+k]*dp[0]+pk*B[i+k])+dp[0]*p0+1=(∑(pk*A[i+k])+p0)dp[0]+∑(pk*B[i+k])+1;明顯A[i]=(∑(pk*A[i+k])+p0)B[i]=∑(pk*B[i+k])+1先遞推求得A[0]和B[0].那么 dp[0]=B[0]/(1-A[0]); */ #include<stdio.h> #include<string.h> #include<iostream> #include<algorithm> using namespace std;double A[600],B[600]; double p[100]; int main() {int T;int k1,k2,k3,a,b,c;int n;scanf("%d",&T);while(T--){scanf("%d%d%d%d%d%d%d",&n,&k1,&k2,&k3,&a,&b,&c);double p0=1.0/k1/k2/k3;memset(p,0,sizeof(p));for(int i=1;i<=k1;i++)for(int j=1;j<=k2;j++)for(int k=1;k<=k3;k++)if(i!=a||j!=b||k!=c)p[i+j+k]+=p0;memset(A,0,sizeof(A));memset(B,0,sizeof(B));for(int i=n;i>=0;i--){A[i]=p0;B[i]=1;for(int j=1;j<=k1+k2+k3;j++){A[i]+=A[i+j]*p[j];B[i]+=B[i+j]*p[j];}}printf("%.16lf\n",B[0]/(1-A[0]));}return 0; }

?

4、HDU? 4405 Aeroplane chess

這題是2012年網(wǎng)絡賽的題目。是很簡單的概率dp.轉移方程很好想到。

求期望。按照公式從后望前遞推就可以得到答案了。

解題報告here

HDU 4405 /*概率DP求期望。 形成一個有向無環(huán)圖。按照公式遞推就可以了。 dp[i]表示i點跳到目標狀態(tài)的期望步數(shù)*/#include<stdio.h> #include<iostream> #include<algorithm> #include<string.h> #include<vector> using namespace std;const int MAXN=100010; double dp[MAXN]; vector<int>vec[MAXN]; bool used[MAXN]; int main() {int n,m;int u,v;while(scanf("%d%d",&n,&m)){if(n==0&&m==0)break;for(int i=0;i<=n;i++)vec[i].clear();memset(dp,0,sizeof(dp));while(m--){scanf("%d%d",&u,&v);vec[v].push_back(u);}memset(used,false,sizeof(used));for(int i=0;i<vec[n].size();i++){v=vec[n][i];dp[v]=0;used[v]=true;}for(int i=n-1;i>=0;i--){if(used[i]==false){for(int j=i+1;j<=i+6;j++)dp[i]+=dp[j]/6;dp[i]+=1;used[i]=true;}for(int j=0;j<vec[i].size();j++){v=vec[i][j];dp[v]=dp[i];used[v]=true;}}printf("%.4lf\n",dp[0]);}return 0; }

?

?5、HDU 4089 Activation

這題是求概率，但是也有種求期望的感覺，都是要列出公式來，化簡，遞推出答案。

2011年北京現(xiàn)場賽的題目。再比賽時做出來確實不容易，需要對概率DP很熟悉才能做出來。

解題報告見here

HDU 4089 /* HDU 4098 題意：有n個人排隊等著在官網(wǎng)上激活游戲。Tomato排在第m個。 對于隊列中的第一個人。有一下情況： 1、激活失敗，留在隊列中等待下一次激活（概率為p1) 2、失去連接，出隊列，然后排在隊列的最后（概率為p2） 3、激活成功，離開隊列（概率為p3） 4、服務器癱瘓，服務器停止激活，所有人都無法激活了。 求服務器癱瘓時Tomato在隊列中的位置<=k的概率解析： 概率DP； 設dp[i][j]表示i個人排隊,Tomato排在第j個位置，達到目標狀態(tài)的概率(j<=i) dp[n][m]就是所求 j==1: dp[i][1]=p1*dp[i][1]+p2*dp[i][i]+p4; 2<=j<=k: dp[i][j]=p1*dp[i][j]+p2*dp[i][j-1]+p3*dp[i-1][j-1]+p4; k<j<=i: dp[i][j]=p1*dp[i][j]+p2*dp[i][j-1]+p3*dp[i-1][j-1]; 化簡： j==1: dp[i][1]=p*dp[i][i]+p41; 2<=j<=k: dp[i][j]=p*dp[i][j-1]+p31*dp[i-1][j-1]+p41; k<j<=i: dp[i][j]=p*dp[i][j-1]+p31*dp[i-1][j-1];其中: p=p2/(1-p1); p31=p3/(1-p1) p41=p4/(1-p1)可以循環(huán)i=1->n 遞推求解dp[i].在求解dp[i]的時候dp[i-1]就相當于常數(shù)了。 在求解dp[i][1~i]時等到下列i個方程 j==1: dp[i][1]=p*dp[i][i]+c[1]; 2<=j<=k:dp[i][j]=p*dp[i][j-1]+c[j]; k<j=i: dp[i][j]=p*dp[i][j]+c[j]; 其中c[j]都是常數(shù)了。上述方程可以解出dp[i]了。 首先是迭代得到 dp[i][i].然后再代入就可以得到所有的dp[i]了。注意特判一種情況。就是p4<eps時候，就不會崩潰了，應該直接輸出0 */ #include<stdio.h> #include<iostream> #include<math.h> #include<algorithm> #include<string.h> using namespace std;const int MAXN=2020; const double eps=1e-5; double c[MAXN]; double pp[MAXN]; double dp[MAXN][MAXN]; int main() {int n,m,k;double p1,p2,p3,p4;while(scanf("%d%d%d%lf%lf%lf%lf",&n,&m,&k,&p1,&p2,&p3,&p4)!=EOF){if(p4<eps){printf("0.00000\n");continue;}double p=p2/(1-p1);double p41=p4/(1-p1);double p31=p3/(1-p1);pp[0]=1.0;//pp[i]=p^1;for(int i=1;i<=n;i++) pp[i]=p*pp[i-1];dp[1][1]=p41/(1-p);c[1]=p41;for(int i=2;i<=n;i++){for(int j=2;j<=k;j++)c[j]=p31*dp[i-1][j-1]+p41;for(int j=k+1;j<=i;j++) c[j]=p31*dp[i-1][j-1];double tmp=c[1]*pp[i-1];for(int j=2;j<=k;j++)tmp+=c[j]*pp[i-j];for(int j=k+1;j<=i;j++)tmp+=c[j]*pp[i-j];dp[i][i]=tmp/(1-pp[i]);dp[i][1]=p*dp[i][i]+c[1];for(int j=2;j<i;j++)dp[i][j]=p*dp[i][j-1]+c[j];}printf("%.5lf\n",dp[n][m]);}return 0; }

?

6、HDU 4035 Maze

經(jīng)典的的概率DP的題目。做了可以體會到dp 求期望的一類的方法。

解題報告見here

HDU 4035 /* HDU 4035 kuangbin http://www.cnblogs.com/kuangbin/dp求期望的題。題意：有n個房間，由n-1條隧道連通起來，實際上就形成了一棵樹，從結點1出發(fā)，開始走，在每個結點i都有3種可能：1.被殺死，回到結點1處（概率為ki）2.找到出口，走出迷宮 （概率為ei）3.和該點相連有m條邊，隨機走一條求：走出迷宮所要走的邊數(shù)的期望值。設 E[i]表示在結點i處，要走出迷宮所要走的邊數(shù)的期望。E[1]即為所求。葉子結點：E[i] = ki*E[1] + ei*0 + (1-ki-ei)*(E[father[i]] + 1);= ki*E[1] + (1-ki-ei)*E[father[i]] + (1-ki-ei);非葉子結點：（m為與結點相連的邊數(shù)）E[i] = ki*E[1] + ei*0 + (1-ki-ei)/m*( E[father[i]]+1 + ∑( E[child[i]]+1 ) );= ki*E[1] + (1-ki-ei)/m*E[father[i]] + (1-ki-ei)/m*∑(E[child[i]]) + (1-ki-ei);設對每個結點：E[i] = Ai*E[1] + Bi*E[father[i]] + Ci;對于非葉子結點i，設j為i的孩子結點，則∑(E[child[i]]) = ∑E[j]= ∑(Aj*E[1] + Bj*E[father[j]] + Cj)= ∑(Aj*E[1] + Bj*E[i] + Cj)帶入上面的式子得(1 - (1-ki-ei)/m*∑Bj)*E[i] = (ki+(1-ki-ei)/m*∑Aj)*E[1] + (1-ki-ei)/m*E[father[i]] + (1-ki-ei) + (1-ki-ei)/m*∑Cj;由此可得Ai = (ki+(1-ki-ei)/m*∑Aj) / (1 - (1-ki-ei)/m*∑Bj);Bi = (1-ki-ei)/m / (1 - (1-ki-ei)/m*∑Bj);Ci = ( (1-ki-ei)+(1-ki-ei)/m*∑Cj ) / (1 - (1-ki-ei)/m*∑Bj);對于葉子結點Ai = ki;Bi = 1 - ki - ei;Ci = 1 - ki - ei;從葉子結點開始，直到算出 A1,B1,C1;E[1] = A1*E[1] + B1*0 + C1;所以E[1] = C1 / (1 - A1);若 A1趨近于1則無解...*/ #include<stdio.h> #include<string.h> #include<algorithm> #include<iostream> #include<math.h> #include<vector> using namespace std; const int MAXN=10010; const double eps=1e-9;//這里1e-8會WA。設為1e-9和1e-10可以 double k[MAXN],e[MAXN]; double A[MAXN],B[MAXN],C[MAXN];vector<int>vec[MAXN];//存樹bool dfs(int t,int pre)//t的根結點是pre {int m=vec[t].size();//點t的度A[t]=k[t];B[t]=(1-k[t]-e[t])/m;C[t]=1-k[t]-e[t];double tmp=0;for(int i=0;i<m;i++){int v=vec[t][i];if(v==pre)continue;if(!dfs(v,t))return false;A[t]+=(1-k[t]-e[t])/m*A[v];C[t]+=(1-k[t]-e[t])/m*C[v];tmp+=(1-k[t]-e[t])/m*B[v];}if(fabs(tmp-1)<eps)return false;A[t]/=(1-tmp);B[t]/=(1-tmp);C[t]/=(1-tmp);return true; } int main() {// freopen("in.txt","r",stdin);// freopen("out.txt","w",stdout);int T;int n;int u,v;int iCase=0;scanf("%d",&T);while(T--){iCase++;scanf("%d",&n);for(int i=1;i<=n;i++)vec[i].clear();for(int i=1;i<n;i++){scanf("%d%d",&u,&v);vec[u].push_back(v);vec[v].push_back(u);}for(int i=1;i<=n;i++){scanf("%lf%lf",&k[i],&e[i]);k[i]/=100;e[i]/=100;}printf("Case %d: ",iCase);if(dfs(1,-1)&&fabs(1-A[1])>eps){printf("%.6lf\n",C[1]/(1-A[1]));}else printf("impossible\n");} }

?

?7、HDU 3853 LOOPS

?比較簡單的概率DP了，入門基礎題。

注意一個小陷進。

解題報告here

HDU 3853 /* HDU 3853解析： 設dp[i][j]表示(i,j)到(R,C)需要消耗的能量 則： dp[i][j]=p1[i][j]*dp[i][j]+p2[i][j]*dp[i][j+1]+p3[i][j]*dp[i+1][j]+2; 化簡得到： dp[i][j]=p2[i][j]*dp[i][j+1]/(1-p1[i][j])+p3[i][j]*dp[i+1][j]/(1-p1[i][j])+2/(1-p1[i][j]); 注意一種情況就是p1[i][j]==1的情況。 題目只是保證答案小于1000000.但是有的點可能永遠都不可能到達的。 所以這樣的點出現(xiàn)p1[i][j]是允許的。 否則就會WA了。 */ #include<stdio.h> #include<iostream> #include<algorithm> #include<string.h> #include<math.h> using namespace std; const int MAXN=1010; const double eps=1e-5; double dp[MAXN][MAXN]; double p1[MAXN][MAXN]; double p2[MAXN][MAXN]; double p3[MAXN][MAXN];int main() {int R,C;while(scanf("%d%d",&R,&C)!=EOF){for(int i=1;i<=R;i++)for(int j=1;j<=C;j++)scanf("%lf%lf%lf",&p1[i][j],&p2[i][j],&p3[i][j]);dp[R][C]=0;for(int i=R;i>=1;i--)for(int j=C;j>=1;j--){if(i==R&&j==C)continue;if(fabs(1-p1[i][j])<eps)continue;dp[i][j]=p2[i][j]/(1-p1[i][j])*dp[i][j+1]+p3[i][j]/(1-p1[i][j])*dp[i+1][j]+2/(1-p1[i][j]);}printf("%.3lf\n",dp[1][1]);}return 0; }

?

8、POJ 2151 Check the difficulty of problems

此題還不算是概率DP的題目。就是DP題，求概率。

想到轉移方程就不難了。

題解見here

POJ 2151 /* POJ 2151 題意： ACM比賽中，共M道題，T個隊，pij表示第i隊解出第j題的概率 問 每隊至少解出一題且冠軍隊至少解出N道題的概率。解析：DP 設dp[i][j][k]表示第i個隊在前j道題中解出k道的概率 則： dp[i][j][k]=dp[i][j-1][k-1]*p[j][k]+dp[i][j-1][k]*(1-p[j][k]); 先初始化算出dp[i][0][0]和dp[i][j][0]; 設s[i][k]表示第i隊做出的題小于等于k的概率 則s[i][k]=dp[i][M][0]+dp[i][M][1]+``````+dp[i][M][k];則每個隊至少做出一道題概率為P1=(1-s[1][0])*(1-s[2][0])*```(1-s[T][0]); 每個隊做出的題數(shù)都在1~N-1的概率為P2=(s[1][N-1]-s[1][0])*(s[2][N-1]-s[2][0])*```(s[T][N-1]-s[T][0]);最后的答案就是P1-P2 */ #include<stdio.h> #include<string.h> #include<algorithm> #include<iostream> #include<math.h> using namespace std;double dp[1010][50][50]; double s[1010][50]; double p[1010][50]; int main() {int M,N,T;while(scanf("%d%d%d",&M,&T,&N)!=EOF){if(M==0&&T==0&&N==0)break;for(int i=1;i<=T;i++)for(int j=1;j<=M;j++)scanf("%lf",&p[i][j]);for(int i=1;i<=T;i++){dp[i][0][0]=1;for(int j=1;j<=M;j++)dp[i][j][0]=dp[i][j-1][0]*(1-p[i][j]);for(int j=1;j<=M;j++)for(int k=1;k<=j;k++)dp[i][j][k]=dp[i][j-1][k-1]*p[i][j]+dp[i][j-1][k]*(1-p[i][j]);s[i][0]=dp[i][M][0];for(int k=1;k<=M;k++)s[i][k]=s[i][k-1]+dp[i][M][k];}double P1=1;double P2=1;for(int i=1;i<=T;i++){P1*=(1-s[i][0]);P2*=(s[i][N-1]-s[i][0]);}printf("%.3lf\n",P1-P2);}return 0; }

?

?9、Codeforces? 148D Bag of mice

抓老鼠問題。轉移方程要思考下就出來了。

解題報告here

CF 148D /* CF 148D 題意： 原來袋子里有w只白鼠和b只黑鼠 龍和王妃輪流從袋子里抓老鼠。誰先抓到白色老師誰就贏。 王妃每次抓一只老鼠，龍每次抓完一只老鼠之后會有一只老鼠跑出來。 每次抓老鼠和跑出來的老鼠都是隨機的。 如果兩個人都沒有抓到白色老鼠則龍贏。王妃先抓。 問王妃贏的概率。解析： 設dp[i][j]表示現(xiàn)在輪到王妃抓時有i只白鼠，j只黑鼠，王妃贏的概率 明顯 dp[0][j]=0,0<=j<=b;因為沒有白色老鼠了dp[i][0]=1,1<=i<=w;因為都是白色老鼠，抓一次肯定贏了。dp[i][j]可以轉化成下列四種狀態(tài)：1、王妃抓到一只白鼠，則王妃贏了，概率為i/(i+j);2、王妃抓到一只黑鼠，龍抓到一只白色，則王妃輸了，概率為j/(i+j)*i/(i+j-1).3、王妃抓到一只黑鼠，龍抓到一只黑鼠，跑出來一只黑鼠，則轉移到dp[i][j-3]。概率為j/(i+j)*(j-1)/(i+j-1)*(j-2)/(i+j-2);4、王妃抓到一只黑鼠，龍抓到一只黑鼠，跑出來一只白鼠，則轉移到dp[i-1][j-2].概率為j/(i+j)*(j-1)/(i+j-1)*i/(i+j-2);當然后面兩種情況要保證合法，即第三種情況要至少3只黑鼠，第四種情況要至少2只白鼠 */#include<stdio.h> #include<iostream> #include<algorithm> #include<string.h> #include<math.h> using namespace std; const int MAXN=1010; double dp[MAXN][MAXN]; int main() {int w,b;while(scanf("%d%d",&w,&b)!=EOF){memset(dp,0,sizeof(dp));for(int i=0;i<=b;i++)dp[0][i]=0;for(int i=1;i<=w;i++)dp[i][0]=1;for(int i=1;i<=w;i++)for(int j=1;j<=b;j++){dp[i][j]+=(double)i/(i+j);//直接抓到白的if(j>=3)//抓到黑的，另外一個人也是抓到黑的，跑出一個黑的dp[i][j]+=(double)j/(i+j)*((double)(j-1)/(i+j-1))*((double)(j-2)/(i+j-2))*dp[i][j-3];if(j>=2) //抓到黑的，另外一個人也是抓到黑的，跑出一個白的dp[i][j]+=((double)j/(i+j))*((double)(j-1)/(i+j-1))*((double)i/(i+j-2))*dp[i-1][j-2];}printf("%.9lf\n",dp[w][b]);}return 0; }

?

10、POJ 3071 Football

足球賽的淘汰賽問題。問最后勝利的概率最大的球隊。

簡單概率DP

題解報告見here

POJ 3071 /* POJ 3071 題意：2^n個隊進行足球賽，每個隊打敗另外一個隊都有一個概率。 問最后勝利的概率最大的是哪只球隊。概率公式，dp算一下就可以了。 */ #include<stdio.h> #include<iostream> #include<algorithm> #include<string.h> using namespace std;double dp[8][200];//dp[i][j]表示在第i場比賽中j勝出的概率 double p[200][200]; int main() {int n;while(scanf("%d",&n)!=EOF){if(n==-1)break;memset(dp,0,sizeof(dp));for(int i=0;i<(1<<n);i++)for(int j=0;j<(1<<n);j++)scanf("%lf",&p[i][j]);//cin>>p[i][j];for(int i=0;i<(1<<n);i++)dp[0][i]=1;for(int i=1;i<=n;i++)//2^n個人要進行n場比賽 {for(int j=0;j<(1<<n);j++){int t=j/(1<<(i-1));t^=1;dp[i][j]=0;for(int k=t*(1<<(i-1));k<t*(1<<(i-1))+(1<<(i-1));k++)dp[i][j]+=dp[i-1][j]*dp[i-1][k]*p[j][k];}}int ans;double temp=0;for(int i=0;i<(1<<n);i++){if(dp[n][i]>temp){ans=i;temp=dp[n][i];}}printf("%d\n",ans+1);}return 0; }

?

?11、SGU? 495 Kids and Prizes?

簡單的概率DP。　　O（1）,推公式就可以出來。

解題報告here

SGU 495 /* SGU 495 題意：n個盒子里裝有禮物，m個人隨機選擇禮物，選完之后空盒子放回 問選中的禮物數(shù)的期望。m個人是獨立的。 對于每個禮物不被人選中的概率為((n-1)/n)^m 那么不被選中的禮物數(shù)的期望就是 n*((n-1)/n)^m 所以答案就是 n-n*((n-1)/n)^m;*/ #include<stdio.h> #include<iostream> #include<algorithm> #include<math.h> using namespace std; int main() {int n,m;while(scanf("%d%d",&n,&m)!=EOF){double p=(double)(n-1)/n;double ans=n-n*pow(p,m);printf("%.10lf\n",ans);}return 0; }

?

?12、ZOJ? 3380 Patchouli's Spell Cards

用JAVA的大樹做的概率DP。有m個位置，每個位置填入1~n中的一個數(shù)，求至少有L個數(shù)一樣的概率。

解題報告見here

ZOJ 3380 /** ZOJ 3380* 題目意思：有m個位置，每個位置填入一個數(shù)，數(shù)的范圍是1~n,問至少有L個位置的數(shù)一樣的概率* 輸出要是最簡分數(shù)的形式，所以用大數(shù)JAVA* 至少有L個位置一樣，就是L，L+1，L+2····m個位置一樣。* 我們從反面來考慮，總數(shù)是n^m，我們求沒有L個位置一樣的數(shù)的概率* 設 dp[i][j]表示用前i個數(shù)，填充j個位置的方案數(shù)（要符合沒有L個位置是一樣的數(shù))* dp[i][j]=dp[i-1][j]+Sigm( dp[i-1][j-k]*C[m-(j-k)][k] ) k<=j&&k<L* 其實就是看第i個數(shù)，可以不填，填一個位置，兩個位置······這樣累加過來。* 那么最后的答案就是 (n^m-dp[1~n][m])/(n^m)*/ import java.util.*; import java.io.*; import java.math.*; public class Main {static BigInteger[][] dp=new BigInteger[110][110];static BigInteger[][] C=new BigInteger[110][110];//組合數(shù)public static void main(String arg[]){Scanner cin=new Scanner(new BufferedInputStream(System.in));for(int i=0;i<105;i++){C[i][0]=C[i][i]=BigInteger.ONE;for(int j=1;j<i;j++)C[i][j]=C[i-1][j-1].add(C[i-1][j]);}int N,M,L;while(cin.hasNext()){M=cin.nextInt();N=cin.nextInt();L=cin.nextInt();BigInteger tol=BigInteger.valueOf(N).pow(M);if(L>M){System.out.println("mukyu~");continue;}if(L>M/2)//這個時候可以直接用組合數(shù)求出來 {BigInteger ans=BigInteger.ZERO;for(int i=L;i<=M;i++)ans=ans.add(C[M][i].multiply(BigInteger.valueOf(N-1).pow(M-i)));ans=ans.multiply(BigInteger.valueOf(N));BigInteger gcd=ans.gcd(tol);System.out.println(ans.divide(gcd)+"/"+tol.divide(gcd));continue;}for(int i=0;i<=N;i++)for(int j=0;j<=M;j++){dp[i][j]=BigInteger.ZERO;}dp[0][0]=BigInteger.ONE;for(int i=1;i<=N;i++)for(int j=1;j<=M;j++){for(int k=0;k<L&&k<=j;k++)dp[i][j]=dp[i][j].add(dp[i-1][j-k].multiply(C[M-(j-k)][k]));}BigInteger ans=BigInteger.ZERO;for(int i=1;i<=N;i++)ans=ans.add(dp[i][M]); ans=tol.subtract(ans);BigInteger gcd=ans.gcd(tol);System.out.println(ans.divide(gcd)+"/"+tol.divide(gcd));}} }

?

?13、ZOJ 3640? Help Me Escape

比較簡單的概率DP，記憶化搜索很好理解，也很容易寫。

解題報告here

ZOJ 3640 /* 題意： 一只吸血鬼，有n條路給他走，每次他隨機走一條路， 每條路有個限制，如果當時這個吸血鬼的攻擊力大于 等于某個值，那么就會花費t天逃出去，否則，花費1天 的時間，并且攻擊力增加，問他逃出去的期望記憶化搜索做 */#include<stdio.h> #include<iostream> #include<algorithm> #include<string.h> #include<math.h> using namespace std; const int MAXN=200010;double dp[MAXN];int c[110]; int n;double solve(int f) {if(dp[f]>0)return dp[f];dp[f]=0;for(int i=0;i<n;i++){if(f>c[i]){double temp=(1.0+sqrt(5))/2*c[i]*c[i];int t=(int)temp;dp[f]+=(double)t/n;}else{dp[f]+=(1+solve(f+c[i]))/n;}}return dp[f]; } int main() {int f;while(scanf("%d%d",&n,&f)!=EOF){for(int i=0;i<n;i++)scanf("%d",&c[i]);memset(dp,0,sizeof(dp));printf("%.3lf\n",solve(f));}return 0; }

?

?14、HDU 4336 Card Collector

求期望，可以狀態(tài)壓縮概率DP求解。也可以用容斥原理直接求。解題報告here

HDU 4336 /* HDU 4336 題意： 有N(1<=N<=20)張卡片，每包中含有這些卡片的概率為p1,p2,````pN. 每包至多一張卡片，可能沒有卡片。 求需要買多少包才能拿到所以的N張卡片，求次數(shù)的期望。可以用容斥原理做。也可以狀態(tài)壓縮進行概率DP 期望DP */ #include<stdio.h> #include<algorithm> #include<iostream> #include<string.h> using namespace std; const int MAXN=22; double p[MAXN]; double dp[1<<MAXN]; int main() {int n;while(scanf("%d",&n)!=EOF){double tt=0;for(int i=0;i<n;i++){scanf("%lf",&p[i]);tt+=p[i];}tt=1-tt;//tt就表示沒有卡片的概率了dp[(1<<n)-1]=0;for(int i=(1<<n)-2;i>=0;i--){double x=0,sum=1;for(int j=0;j<n;j++){if((i&(1<<j)))x+=p[j];else sum+=p[j]*dp[i|(1<<j)];}dp[i]=sum/(1-tt-x);}printf("%.5lf\n",dp[0]);}return 0; } HDU 4336 /* HDU 4336 容斥原理 位元素枚舉 */ #include<stdio.h> #include<string.h> #include<iostream> #include<algorithm> using namespace std;double p[22]; int main() {int n;while(scanf("%d",&n)==1){for(int i=0;i<n;i++)scanf("%lf",&p[i]);double ans=0;for(int i=1;i<(1<<n);i++){int cnt=0;double sum=0;for(int j=0;j<n;j++)if(i&(1<<j)){sum+=p[j];cnt++;}if(cnt&1)ans+=1.0/sum;else ans-=1.0/sum;}printf("%.5lf\n",ans);}return 0; }

?

?

下面介紹的三題是用高斯消元法求解的概率DP

15、ZJUT 1423?地下迷宮

?一個N*M的迷宮，除了障礙外等概率走，求起點走到終點步數(shù)的期望。先在起點進行bfs，找出所以可以到達的點并編號，然后建立方程組求解。

ZJUT 1423 /*地下迷宮Description: 由于山體滑坡，DK被困在了地下蜘蛛王國迷宮。為了搶在DH之前來 到TFT，DK必須盡快走出此迷宮。此迷宮僅有一個出口，而由于大BOSS 的力量減弱影響到了DK，使DK的記憶力嚴重下降，他甚至無法記得他 上一步做了什么。所以他只能每次等概率隨機的選取一個方向走。 當然他不會選取周圍有障礙的地方走。如DK周圍只有兩處空地，則每 個都有1/2的概率。現(xiàn)在要求他平均要走多少步可以走出此迷宮。Input: 先是一行兩個整數(shù)N, M(1<=N, M<=10)表示迷宮為N*M大小， 然后是N行，每行M個字符，'.'表示是空地，'E’表示出口，'D’表示DK，'X’表示障礙。 Output: 如果DK無法走出或要超過1000000步才能走出，輸出tragedy!， 否則輸出一個實數(shù)表示平均情況下DK要走幾步可以走出迷宮，四舍五入到小數(shù)點后兩位。 Sample Input: 1 2 ED 3 3 D.X .X. X.E Sample Output: 1.00 tragedy!首先對地圖節(jié)點重新標號。假設E[i]表示DK從i點開始走出迷宮的期望值。 那么E[i]=(E[a1]+E[a2]+E[a3]+...+E[an])/n+1，其中a1...an是i的相鄰節(jié)點。 那么對于每一個DK可達的節(jié)點來說，都可以為它建立這樣的一個方程。現(xiàn) 在假設DK可達的點有N個，那么我們最終將會得到N元一次方程組。最后 利用高斯消元解出E[No[S]]。其中S是DK的起點，No[S]是重標號后的起點 這里要重點注意的是，我們聯(lián)立方程的時候，一定要注意DK可達這個條件， 不然就會導致無解的情況。*/ #include<stdio.h> #include<iostream> #include<algorithm> #include<string.h> #include<queue> #include<math.h> using namespace std;#define eps 1e-9 const int MAXN=200; double a[MAXN][MAXN],x[MAXN];//方程的左邊的矩陣和等式右邊的值，求解之后x存的就是結果 int equ,var;//方程數(shù)和未知數(shù)個數(shù)int Gauss() {int i,j,k,col,max_r;for(k=0,col=0;k<equ&&col<var;k++,col++){max_r=k;for(i=k+1;i<equ;i++)if(fabs(a[i][col])>fabs(a[max_r][col]))max_r=i;if(fabs(a[max_r][col])<eps)return 0;if(k!=max_r){for(j=col;j<var;j++)swap(a[k][j],a[max_r][j]);swap(x[k],x[max_r]);}x[k]/=a[k][col];for(j=col+1;j<var;j++)a[k][j]/=a[k][col];a[k][col]=1;for(i=0;i<equ;i++)if(i!=k){x[i]-=x[k]*a[i][k];for(j=col+1;j<var;j++)a[i][j]-=a[k][j]*a[i][col];a[i][col]=0;}}return 1; }char map[20][20]; int num[20][20]; struct Node {int x,y; }; int sx,sy,ex,ey; int n,m; int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}}; int cnt;void bfs() {memset(num,-1,sizeof(num));cnt=0;num[sx][sy]=cnt++;queue<Node>que;Node temp;Node tt;temp.x=sx;temp.y=sy;que.push(temp);while(!que.empty()){temp=que.front();que.pop();for(int i=0;i<4;i++){tt.x=temp.x+dir[i][0];tt.y=temp.y+dir[i][1];if(tt.x>=0&&tt.x<n&&tt.y>=0&&tt.y<m&&map[tt.x][tt.y]!='X'&&num[tt.x][tt.y]==-1){num[tt.x][tt.y]=cnt++;que.push(tt);}}} } int main() {//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);while(scanf("%d%d",&n,&m)!=EOF){for(int i=0;i<n;i++){scanf("%s",&map[i]);for(int j=0;j<m;j++){if(map[i][j]=='D'){sx=i;sy=j;}if(map[i][j]=='E'){ex=i;ey=j;}}}bfs();if(num[ex][ey]==-1){printf("tragedy!\n");continue;}memset(a,0,sizeof(a));memset(x,0,sizeof(x));equ=var=cnt;for(int i=0;i<n;i++)for(int j=0;j<m;j++)if(num[i][j]!=-1){int now=num[i][j];if(map[i][j]=='E'){memset(a[now],0,sizeof(a[now]));x[now]=0;a[now][now]=1;continue;}int Count=0;for(int k=0;k<4;k++){int tx=i+dir[k][0];int ty=j+dir[k][1];if(tx>=0&&tx<n&&ty>=0&&ty<m&&map[tx][ty]!='X'&&num[tx][ty]!=-1){a[now][num[tx][ty]]=-1;Count++;}a[now][now]=Count;x[now]=Count;}}if(Gauss()){if(x[num[sx][sy]]<=1000000)printf("%.2lf\n",x[num[sx][sy]]);else printf("tragedy!\n");}else printf("tragedy!\n");}return 0; }

?

16、ZJUT 1317 擲飛盤

在一個環(huán)上拋擲兩個飛盤?，每個飛盤等概率往左和右走，問兩個飛盤走到同一個地方所需要步數(shù)的期望。

按照他們的距離表示狀態(tài)進行概率DP。dp[i]=dp[i-2]/4+dp[i+2]/4+dp[i]/2+1.整理下就出來方程。注意是循環(huán)的，要進行處理。

ZJUT 1317 /* ZJUT 1317 擲飛盤Description: m個人位于正m邊形的頂點上，彼此拋擲飛盤。他們共有兩個飛盤， 且開始時這兩個飛盤位于相距為n的兩個人的手中（相鄰兩個人 相距為1，依此類推）。在每次拋擲時兩個飛盤被同時拋出，飛盤都 以1/2的概率被拋到擲飛盤的人左邊相鄰的人，1/2的概率被拋到 右邊相鄰的人。此過程一直進行，直到兩個飛盤被擲到同一個人 手中，求此拋擲飛盤的游戲平均情況下(期望)會在拋擲幾次后結束。Input: 每行有兩個整數(shù)m (2<m<=100)，n (0 < n < m)。 Output: 對每組數(shù)據(jù)m,n，輸出平均所需步數(shù)(四舍五入，保留兩位小數(shù)）， 如果有限步內不可能結束就輸出INF。Sample Input: 3 1 4 1 Sample Output: 4.00 INF*/ #include<stdio.h> #include<iostream> #include<algorithm> #include<string.h> #include<queue> #include<math.h> using namespace std;#define eps 1e-9 const int MAXN=200; double a[MAXN][MAXN],x[MAXN];//方程的左邊的矩陣和等式右邊的值，求解之后x存的就是結果 int equ,var;//方程數(shù)和未知數(shù)個數(shù)int Gauss() {int i,j,k,col,max_r;for(k=0,col=0;k<equ&&col<var;k++,col++){max_r=k;for(i=k+1;i<equ;i++)if(fabs(a[i][col])>fabs(a[max_r][col]))max_r=i;if(fabs(a[max_r][col])<eps)return 0;if(k!=max_r){for(j=col;j<var;j++)swap(a[k][j],a[max_r][j]);swap(x[k],x[max_r]);}x[k]/=a[k][col];for(j=col+1;j<var;j++)a[k][j]/=a[k][col];a[k][col]=1;for(i=0;i<equ;i++)if(i!=k){x[i]-=x[k]*a[i][k];for(j=col+1;j<var;j++)a[i][j]-=a[k][j]*a[i][col];a[i][col]=0;}}return 1; }int n,m; int num[MAXN]; int cnt; int getnum(int x) {x=(x%n+n)%n;if(x>n-x)x=n-x;return x; } void dfs(int x) {x=getnum(x);num[x]=cnt++;int y=getnum(x+2);if(num[y]==-1)dfs(y);y=getnum(x-2);if(num[y]==-1)dfs(y); } int main() {while(scanf("%d%d",&n,&m)!=EOF){memset(num,-1,sizeof(num));cnt=0;m=getnum(m);dfs(m);if(num[0]==-1){printf("INF\n");continue;}memset(a,0,sizeof(a));memset(x,0,sizeof(x));for(int i=0;i<n;i++)if(num[i]!=-1){int now=num[i];a[now][now]=2;x[now]=4;int t=getnum(i-2);a[now][num[t]]-=1;//這里一定要注意的，要減1，不能直接賦值為-1，t=getnum(i+2);//因為i-2和i+2是可能一樣的a[now][num[t]]-=1;}int t=num[0];memset(a[t],0,sizeof(a[t]));a[t][t]=1;x[t]=0;equ=var=cnt;//這個不要忘記了，經(jīng)常忘掉！！！if(Gauss())printf("%.2lf\n",x[num[m]]);else printf("INF\n");}return 0; }

?

?

17、HDU 4418 Time travel

在坐標軸上用高斯消元法求解。注意N=1的時候要特判一下。解題報告here

HDU 4418 /* HDU 4118 題目：給出一個數(shù)軸，有一個起點和一個終點，某個人可以 走1，2，3……m步，每一種情況有一個概率，初始有一個方向， 走到頭則返回，問到達終點的期望步數(shù)為多少。比較明顯的高斯求期望問題Sample Input 2 4 2 0 1 0 50 50 4 1 0 2 1 100Sample Output 8.14 2.00*/ #include<stdio.h> #include<iostream> #include<algorithm> #include<string.h> #include<queue> #include<math.h> using namespace std;#define eps 1e-9 const int MAXN=220; double a[MAXN][MAXN],x[MAXN];//方程的左邊的矩陣和等式右邊的值，求解之后x存的就是結果 int equ,var;//方程數(shù)和未知數(shù)個數(shù)int Gauss() {int i,j,k,col,max_r;for(k=0,col=0;k<equ&&col<var;k++,col++){max_r=k;for(i=k+1;i<equ;i++)if(fabs(a[i][col])>fabs(a[max_r][col]))max_r=i;if(fabs(a[max_r][col])<eps)return 0;if(k!=max_r){for(j=col;j<var;j++)swap(a[k][j],a[max_r][j]);swap(x[k],x[max_r]);}x[k]/=a[k][col];for(j=col+1;j<var;j++)a[k][j]/=a[k][col];a[k][col]=1;for(i=0;i<equ;i++)if(i!=k){x[i]-=x[k]*a[i][k];for(j=col+1;j<var;j++)a[i][j]-=a[k][j]*a[i][col];a[i][col]=0;}}return 1; }int num[MAXN]; double p[MAXN]; int cnt; int n,N;//n=2*N-2 int M; void bfs(int s) {memset(num,-1,sizeof(num));queue<int>que;cnt=0;num[s]=cnt++;que.push(s);while(!que.empty()){int t=que.front();que.pop();for(int i=1;i<=M;i++){if(fabs(p[i])<eps)continue;//這點很重要，這個想到不能達到的點int temp=(t+i)%n;if(num[temp]==-1){num[temp]=cnt++;que.push(temp);}}} } int main() {//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);int s,e;int D;int T;scanf("%d",&T);while(T--){scanf("%d%d%d%d%d",&N,&M,&e,&s,&D);for(int i=1;i<=M;i++){scanf("%lf",&p[i]);p[i]/=100;}if(e==s)//這個特判一定需要，否則可能N==1,會被0除，RE {printf("0.00\n");continue;}n=2*(N-1);if(D==1)s=n-s;bfs(s);if(num[e]==-1&&num[n-e]==-1){printf("Impossible !\n");continue;}equ=var=cnt;memset(a,0,sizeof(a));memset(x,0,sizeof(x));for(int i=0;i<n;i++)if(num[i]!=-1){if(i==e||i==n-e){a[num[i]][num[i]]=1;x[num[i]]=0;continue;}a[num[i]][num[i]]=1;for(int j=1;j<=M;j++){int t=(i+j)%n;if(num[t]!=-1){a[num[i]][num[t]]-=p[j];x[num[i]]+=j*p[j];}}}if(Gauss())printf("%.2lf\n",x[num[s]]);else printf("Impossible !\n");}return 0; }

?

?

?今年概率DP就做到這吧！2012-10-6?

總結

以上是生活随笔為你收集整理的【原创】概率DP总结 by kuangbin的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。