说是期望dp的总结 其实这个我也不是很懂 只是把做了的几道水题的代码贴上来 有时间再补充吧（flag高高立起） 期望dp的dp方程基本上都是倒推的 【没有任何题解】 hdu 3853
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N = 1010; int r,c; double st[N][N],R[N][N],D[N][N]; double f[N][N]; int main(){ scanf("%d%d",&r,&c); for(register int i=1;i<=r;i++){ for(register int j=1;j<=c;j++){ scanf("%lf%lf%lf",&st[i][j],&R[i][j],&D[i][j]); } } f[r][c]=0; for(register int i=r;i>=1;i--){ for(register int j=c;j>=1;j--){ if(i==r&&j==c) continue; if(st[i][j]==1.0) continue; f[i][j]=(D[i][j]*f[i+1][j]+R[i][j]*f[i][j+1]+2.0)/(1-st[i][j]); } } printf("%0.3lf",f[1][1]); return 0; }hdu 4405
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N = 100000+10; int n,m; double f[N]; int a[N],b[N]; double ans=0; int main(){ // printf("2"); while(scanf("%d%d",&n,&m)!=EOF){ if(n+m==0) break; memset(a,-1,sizeof(a)); memset(b,-1,sizeof(b)); memset(f,0,sizeof(f)); while(m--){ int i,x; scanf("%d%d",&i,&x); // if(i>x) b[i]=x; // else a[x]=i; a[i]=x; } f[n]=0; for(int i=n;i>=0;i--){ if(a[i]!=-1) {f[i]+=f[a[i]];continue;}//这个地方我纠结了好久，为什么一定可以保证更新f[i]的时候f[a[i]]一定更新了 //然后跑回去读了原题 0<Xi<Yi<=N 气死我了。。。 if(i==n) continue; f[i]+=1; for(int j=1;j<=6;j++){ f[i]+=(double)1.0*f[i+j]/6; } } /*for(int i=n;i>=0;i--){ if(a[i]!=-1) {f[i]+=f[a[i]];continue;} if(b[i]!=-1) {f[b[i]]+=f[i];continue} if(i==n) continue; f[i]+=1; for(int j=i-1;j>=i-6;j--){ f[j]+=(double)1.0*f[i]/6; } }*///这样写有一个bug 当b[i]的值更新后，那b[i+j] 1<=j<=6也应该更新 所以无法满足无后效性 printf("%0.4lf\n",f[0]);} return 0; }poj 2096
#include<cstdio> #include<cstring> using namespace std; const int N = 1010; int n,s; double dp[N][N];//dp[i][j]表示找到i个分属于j个系统的期望天数 int main(){ scanf("%d%d",&n,&s); dp[n][s] = 0.0; for(int i=n;i>=0;i--){ for(int j=s;j>=0;j--){ if(i==n&&j==s) continue; /* double p1=(double)(i*j)/(n*s); double p2=(double)((n-i)*j)/(n*s); double p3=(double)(i*(s-j))/(n*s); double p4=(double)((n-i)*(s-j))/(n*s); dp[i][j]=1.0*(p2*dp[i+1][j]+p3*dp[i][j+1]+p4*dp[i+1][j+1])/(1-p1);*/ dp[i][j]=(double)1.0*(n*s+(n-i)*j*dp[i+1][j]+i*(s-j)*dp[i][j+1]+(n-i)*(s-j)*dp[i+1][j+1])/(n*s-i*j); } } printf("%0.4lf\n",dp[0][0]); return 0; }这个东西好难啊。
