【POJ 2096】Collecting Bugs

题目传送门：http://poj.org/problem?id=2096

概率dp

#include<iostream>
#include<cstdio>
using namespace std;

const int MAXN = 1000+9;

int n,m;
double f[MAXN][MAXN];

int main(){
	cin>>n>>m;
	for (int i=n;~i;i--) for (int j=m;~j;j--) if (i != n || j != m) 
		f[i][j] = ((double)i*j+(f[i+1][j]+1)*(n-i)*j+(f[i][j+1]+1)*i*(m-j)+(f[i+1][j+1]+1)*(n-i)*(m-j))/(n*m-i*j);
	printf("%.4lf\n",f[0][0]);
	return 0;
}