首页 > 代码库 > 20140907_概率dp
20140907_概率dp
概率dp
假设关系；
递归；
倒着求
POJ 2096
#include <iostream>#include <algorithm>#include <cstdio>#include <cstring>#include <vector>using namespace std;double p[1086][1086];int x,y;double dp(int i,int j){ if(p[i][j]>=0) return p[i][j]; if(i>x||j>y) return 0; if(i==x&&j==y) return 0; double xx=0.0; xx+=dp(i+1,j)*(x-i)*j/x/y; xx+=dp(i,j+1)*(y-j)*i/x/y; xx+=1.0; xx+=dp(i+1,j+1)*(y-j)*(x-i)/x/y; xx/=(1-(double)i*j/x/y); return p[i][j]=xx;}int main(){ while(scanf("%d%d",&x,&y)!=EOF) { for(int i=0;i<x+2;i++) for(int j=0;j<y+3;j++) p[i][j]=-1.0; p[x][y]=0; printf("%.9f\n",dp(0,0)); } return 0;}
有x种bug和y个系统
每次找到的bug有4种情况
1：属于已经找到的bug和系统中的
2：属于已找到的bug但是不属于系统中
3：不属于已找到的bug但是属于系统中的
4：不属于已找到的bug且不属于系统中的
dp[i,j] = p1*dp[i,j] + p2*dp[i+1,j] + p3*dp[i,j+1] + p4*dp[i+1,j+1] + 1;
合并之后
dp[i,j] = ( 1 + p2*dp[i+1,j] + p3*dp[i,j+1] + p4*dp[i+1,j+1] )/( 1-p1 ) ；
然后递归求解（最好不要递归容易爆栈）
HDU 3853
#include <iostream>#include <algorithm>#include <cstdio>#include <cstring>#include <cmath>#define eps 1e-5using namespace std;double p[1086][1086];int x,y;double stay[1086][1086],xia[1086][1086],you[1085][1086];bool vis[1086][1086];double dp(int i,int j){ if(i>=x||j>=y) return 0; if(vis[i][j]) return p[i][j]; vis[i][j]=true; p[i][j]=xia[i][j]*dp(i,j+1)+you[i][j]*dp(i+1,j)+2; if(fabs(1-stay[i][j])<eps) return p[i][j]=0; else return p[i][j]=(p[i][j]/(1-stay[i][j]));}int main(){ while(scanf("%d%d",&x,&y)!=EOF) { memset(vis,false,sizeof vis); memset(p,0,sizeof p); for(int i=0;i<x;i++) { for(int j=0;j<y;j++) { scanf("%lf%lf%lf",&stay[i][j],&xia[i][j],&you[i][j]); } } vis[x-1][y-1]=true; p[x-1][y-1]=0.0; printf("%.3lf\n",dp(0,0)); } return 0;}
一张地图 每次可以三种选择
1：下走
2：右走
3：不动
求到终点的期望
定义
dpij为ij到终点的期望
则dp[ij]=P1dp【ij】+p2dp【ij+1】+p3dp【i+1j】；
化简后转移就行
坑点
if(fabs(1-stay[i][j])<eps) return p[i][j]=0;
由于此点一定不在路径上
所以随便赋值
HDU 4405
#pragma comment(linker, "/STACK:102400000,102400000")#include <iostream>#include <algorithm>#include <cstdio>#include <cstring>#include <cmath>#define eps 1e-5using namespace std;double p[100086];bool vis[100086];int next[100086],n,m;double dp(int x){ if(vis[x]) return p[x]; if(x>=n) return 0; double ret=0.0; for(int i=1;i<7;i++) { int y=x+i; while(next[y]!=-1) y=next[y]; ret+=dp(y); } ret=ret/6+1; vis[x]=1; return p[x]=ret;}int main(){ while(scanf("%d%d",&n,&m),m+n) { memset(vis,false,sizeof vis); memset(next,-1,sizeof next); int a,b; for(int i=0;i<m;i++) scanf("%d%d",&a,&b),next[a]=b; printf("%.4f\n",dp(0)); } return 0;}
飞行棋
每次投点1-6 还有飞行线
和上题一样
ZOJ 3329
#include <iostream>#include <algorithm>#include <cstdio>#include <cstring>#include <cmath>#define eps 1e-5using namespace std;double ap[1086],bp[1086],p[186];int main(){ int T; cin>>T; while(T--) { int n,k1,k2,k3,kkk,a,b,c; scanf("%d%d%d%d%d%d%d",&n,&k1,&k2,&k3,&a,&b,&c); memset(p,0,sizeof p); kkk=k1+k2+k3; double pp; 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) pp=1.0/k1/k2/k3; else p[i+j+k]+=1.0/k1/k2/k3; } } } memset(ap,0,sizeof ap); memset(bp,0,sizeof bp); for(int i=n;i>=0;i--) { for(int j=1;j<=kkk;j++) { ap[i]+=ap[i+j]*p[j]; bp[i]+=bp[i+j]*p[j]; } ap[i]+=pp; bp[i]+=1; } printf("%.10f\n",bp[0]/(1.0-ap[0])); } return 0;}
新类型 化等式求解
http://blog.csdn.net/morgan_xww/article/details/6774708
20140907_概率dp
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。