首页 > 代码库 > 2014 summer day 6 概率dp
2014 summer day 6 概率dp
全期望公式：
全概率公式：
POJ 2096
【题意】：
一个软件有s个子系统，会产生n种bug。
某人一天发现一个bug，这个bug属于某种bug，发生在某个子系统中。
求找到所有的n种bug，且每个子系统都找到bug，这样所要的天数的期望。
【分析】：需要注意的是：bug的数量是无穷大的，所以发现一个bug，出现在某个子系统的概率是1/s，
属于某种类型的概率是1/n。
那么dp[i][j]表示还要找到i个系统，还要找到j种病毒的概率。
具体dp方程看代码。但怎么来说这个dp方程的正确性都怪怪的。
s,n<=1000
【代码】：
1 #include <iostream> 2 #include <stdio.h> 3 #include <math.h> 4 5 using namespace std; 6 7 double dp[1005][1005]; 8 int S,N; 9 int main(){10 while(~scanf("%d%d",&N,&S)){11 double n=N+0.0;12 double s=S+0.0;13 dp[S][N]=0;14 for(int i=S;i>=0;i--){15 for(int j=N;j>=0;j--){16 double ans=1;17 if (i==S && j==N) continue;18 if (i<S) ans+=dp[i+1][j]*(s-i)*j/(s*n);19 if (j<N) ans+=dp[i][j+1]*(n-j)*i/(s*n);20 if (i<S && j<N) ans+=dp[i+1][j+1]*(s-i)*(n-j)/(s*n);21 dp[i][j]=ans/(1.0-i*j/(s*n));22 }23 }24 printf("%.4f\n",dp[0][0]);25 }26 return 0;27 }
HDU 4405
【题意】：
有n个格子，掷色子的掷出的数目就是你一次到移动格数(1--6的点数)。
其中有m个飞行通道可以让你直接从第xi格飞到第yi格。
传送中是连续的，而且不要投骰子
问你走到终点的期望是多少。
【分析】：
dp[i]:开始时处于i位置时要走的期望步数。
一道状态转移要特判的dp，因为一旦从x点可以直接到y点的话，则dp[x]=dp[y];
否则dp[i]=1/6*sigm(dp[i+1]...dp[i+6])+1，i>=N时dp[i]=1;
具体处理看代码。
【代码】：
1 #include <iostream> 2 #include <stdio.h> 3 #include <math.h> 4 5 using namespace std; 6 7 int N,M; 8 int c[100010]; 9 double dp[100010];10 int dfs(int i){11 if (c[i]==i) return c[i];12 else return dfs(c[i]);13 }14 int main(){15 while(~scanf("%d%d",&N,&M)){16 if (N==0 && M==0) break;17 for(int i=0;i<=N;i++){18 c[i]=i;19 }20 for(int i=1;i<=M;i++){21 int x,y;22 scanf("%d%d",&x,&y);23 c[x]=y;24 }25 for(int i=0;i<=N;i++){26 if (c[i]==i) continue;27 else c[i]=dfs(i);28 }29 for(int i=N;i<=N+7;i++) {30 dp[i]=0;31 c[i]=i;32 }33 for(int i=N-1;i>=0;i--){34 double ans=0;35 if (c[i]!=i){36 dp[i]=dp[c[i]];37 continue;38 }39 for(int j=1;j<=6;j++) {40 int x=i+j;41 ans+=dp[c[x]];42 }43 ans=ans*(1/6.0)+1;44 dp[i]=ans;45 }46 printf("%.4f\n",dp[0]);47 }48 return 0;49 }
HDU 4035
【题意】：（%>_<%异次元杀阵有没有）
有n个房间，由n-1条隧道连通起来，实际上就形成了一棵树， 从结点1出发，开始走，在每个结点i都有3种可能： 1.被杀死，回到结点1处（概率为ki） 2.找到出口，走出迷宫 （概率为ei） 3.和该点相连有m条边，随机走一条 求：走出迷宫所要走的边数的期望值。
【分析】：（按照kuangbin的博客推导了一遍，写在本子上，无耻地将之分析粘过来）
设 E[i]表示在结点i处，要走出迷宫所要走的边数的期望。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为与结点相连的边数） 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则无解...
【代码】：
1 /* 2 3 */ 4 #include <iostream> 5 #include <stdio.h> 6 #include <math.h> 7 #include <vector> 8 #define eps 1e-10 9 using namespace std;10 vector<int>G[10010];11 double A[10010];12 double B[10010];13 double C[10010];14 double e[10010],k[10010],p[10010];15 16 int N,K;17 bool dfs(int u,int fa){18 int m=G[u].size();19 double sumA=0,sumB=0,sumC=0;20 for(int i=0;i<m;i++){21 int v=G[u][i];22 if (v==fa) continue;23 if (!dfs(v,u)) return false;24 sumB+=p[u]/m*B[v];25 sumA+=p[u]/m*A[v];26 sumC+=p[u]/m*C[v];27 }28 if (1-sumB<eps) return false;29 A[u]=(k[u]+sumA)/(1-sumB);30 B[u]=p[u]/m/(1-sumB);31 C[u]=(p[u]+sumC)/(1-sumB);32 return true;33 }34 int main(){35 int t;36 scanf("%d",&t);37 for(int cas=1;cas<=t;cas++){38 scanf("%d",&N);39 int u,v;40 for(int i=0;i<=N;i++) G[i].clear();41 for(int i=0;i<N-1;i++){42 scanf("%d%d",&u,&v);43 G[u].push_back(v);44 G[v].push_back(u);45 }46 for(int i=1;i<=N;i++){47 scanf("%lf%lf",&k[i],&e[i]);48 k[i]/=100;49 e[i]/=100;50 p[i]=1-k[i]-e[i];51 }52 printf("Case %d: ",cas);53 if (dfs(1,-1)==false || (1-A[1]<eps)){54 printf("impossible\n");55 }else {56 double ans=C[1]/(1-A[1]);57 printf("%.6f\n",ans);58 }59 }60 return 0;61 }
HDU 3853
【题意】：有一个人被困在一个 R*C(2<=R,C<=1000) 的迷宫中，起初他在 (1,1) 这个点，迷宫的出口是 (R,C)。在迷宫的每一个格子中，他能花费 2 个魔法值开启传送通道。假设他在 (x,y) 这个格子中，开启传送通道之后，有 p_lift[i][j] 的概率被送到 (x,y+1)，有 p_down[i][j] 的概率被送到 (x+1,y)，有 p_loop[i][j] 的概率被送到 (x,y)。问他到出口需要花费的魔法值的期望是多少。
【分析】：DP[i][j]表示现在处在(i,j)点时，需要花费的期望天数
dp[i][j]=mov0*dp[i][j]+mov1*dp[i][j+1]+mov2*dp[i+1][j]+2
写出全期望公式，但是要防止除0的发生，即1-mov0<eps,特判跳过这点就行了。表示不能走到这一点
即：
for(int i=N;i>=1;i--){ for(int j=M;j>=1;j--){ if (vis[i][j]) continue; double ans=2; if (!vis[i][j+1]) ans+=mov[i][j][1]*dp[i][j+1]; if (!vis[i+1][j]) ans+=mov[i][j][2]*dp[i+1][j]; dp[i][j]=ans/(1-mov[i][j][0]); } }
【代码】：
1 /* 2 3 */ 4 #include <iostream> 5 #include <stdio.h> 6 #include <math.h> 7 #include <vector> 8 #include <string.h> 9 #define eps 1e-1010 using namespace std;11 //int a[][2]={{0,0},{0,1},{1,0}};12 double dp[1004][1004];13 double mov[1004][1004][3];14 bool vis[1004][1004];15 int N,M;16 int main(){17 while(~scanf("%d%d",&N,&M)){18 memset(vis,false,sizeof(vis));19 for(int i=1;i<=N;i++){20 for(int j=1;j<=M;j++){21 for(int k=0;k<3;k++){22 scanf("%lf",&mov[i][j][k]);23 if (1-mov[i][j][0]<eps) vis[i][j]=true;24 }25 }26 }27 //dp[i][j]=mov0*dp[i][j]+mov1*dp[i][j+1]+mov2*dp[i+1][j]+2;28 //dp[N][M]=0;29 //dp[1][1]=ans;30 for(int i=0;i<=N+1;i++) dp[i][M+1]=0;31 for(int i=0;i<=M+1;i++) dp[N+1][i]=0;32 for(int i=N;i>=1;i--){33 for(int j=M;j>=1;j--){34 if (vis[i][j]) continue;35 double ans=2;36 if (!vis[i][j+1]) ans+=mov[i][j][1]*dp[i][j+1];37 if (!vis[i+1][j]) ans+=mov[i][j][2]*dp[i+1][j];38 dp[i][j]=ans/(1-mov[i][j][0]);39 }40 }41 printf("%.3f\n",dp[1][1]);42 }43 return 0;44 }
POJ 3071
【题意】：
2^n支球队按照竞赛图踢足球，
给你任意两支球队相互之间踢赢的概率，
求最后那支球队最可能夺冠。
【分析】：每轮剩下的队伍是一定的，而且到底和谁PK也是一定的，按竞赛图枚举即可
//dp[i][j] = ∑dp[i-1][k]*p[j][k]*dp[i-1][j]
//k表示可能与j 比赛的队伍,那么k有哪些呢？
//当i=1时，和1
//当i=2时，和3,4
//当i=3时，和5,6,7,8
//就是 2^(i-1)+1---->2^(i)
【代码】：
1 /* 2 题意：2^n支球队按照竞赛图踢足球， 3 给你任意两支球队相互之间踢赢的概率， 4 求最后那支球队最可能夺冠。 5 */ 6 #include <iostream> 7 #include <stdio.h> 8 #include <math.h> 9 #include <vector>10 #include <string.h>11 #define eps 1e-1012 using namespace std;13 //dp[i][j] = ∑dp[i-1][k]*p[j][k]*dp[i-1][j]14 //k表示可能与j 比赛的队伍,那么k有哪些呢？15 //当i=1时，和116 //当i=2时，和3,417 //当i=3时，和5,6,7,818 //就是 2^(i-1)+1---->2^(i)19 double dp[10][150];20 double p[150][150];21 int N;22 int main(){23 while(~scanf("%d",&N)&& N!=-1){24 for(int i=0;i<(1<<N);i++){25 dp[0][i]=1;26 }27 for(int i=0;i<(1<<N);i++){28 for(int j=0;j<(1<<N);j++){29 scanf("%lf",&p[i][j]);30 }31 }32 for(int i=1;i<=N;i++){33 for(int j=0;j<(1<<N);j++){34 dp[i][j]=0;35 for(int k=0;k<(1<<N);k++){36 if(((j>>(i-1))^1)==(k>>(i-1))){37 dp[i][j]+=dp[i-1][k]*dp[i-1][j]*p[j][k];38 // cout<<i<<","<<j<<","<<k<<":"<<dp[i][j]<<endl;39 }40 }41 }42 }43 double m=-1;44 int ans=-1;45 for(int i=0;i<(1<<N);i++){46 if (dp[N][i]>m){47 m=dp[N][i];48 ans=i;49 }50 }51 printf("%d\n",ans+1);52 }53 return 0;54 }
SGU 495
【题意】：
ZOJ 3640
【题意】：
POJ 3744
【题意】：
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。