题目地址：POJ 2096
第一发概率DP。详情看这篇博客，讲的很清楚了。
代码如下：
#include #include #include #include #include #include #include #include #include using namespace std; #define LL __int64 #define pi acos(-1.0) const int mod=100000000; const int INF=0x3f3f3f3f; const double eqs=1e-8; double dp[1005][1005]; int main() { int i, j, n, m; double p0, p1, p2, p3; while(scanf("%d%d",&n,&m)!=EOF){ dp[n][m]=0; for(i=n;i>=0;i--){ for(j=m;j>=0;j--){ if(i==n&&j==m) continue ; p1=(n-i)*(m-j)*1.0; p2=(n-i)*j*1.0; p3=i*(m-j)*1.0; dp[i][j]=(p1*dp[i+1][j+1]+p2*dp[i+1][j]+p3*dp[i][j+1]+n*m)/(n*m-i*j); } } printf("%.4f\n",dp[0][0]); } return 0; }