http://codeforces.com/problemset/problem/399/D
题意：给出n和m，表示在一个n*n的平面上有n*n个方格，其中有m块已经涂色。现在随机选中一块进行涂色（如果已经涂色跳过，也消耗时间），消耗1个步骤。终止条件为每行每列都有至少有一块瓷砖被涂色。问说涂成满意的情况需要时间的期望。
思路：把整个方格分成四部分，如果选择左上角上的一块，那么行和列都将被涂上一个；右上角的话，行被涂上一个，列不变；左下角的话，行不变，列被涂上一个；右下角，行列都不变。
状态转移方程：dp[i][j]=(dp[i+1][j]*(n-i)*j+dp[i][j+1]*(n-j)*i+dp[i+1][j+1]*(n-i)*(n-j)+n*n)/(n*n-i*j);
1 #include <cstdio> 2 #include <iostream> 3 #include <cstring> 4 #include <algorithm> 5 #define LL __int64 6 using namespace std; 7 8 int n,m; 9 int nr[2010],nc[2010]; 10 double dp[2010][2010]; 11 12 int main() 13 { 14 scanf("%d%d",&n,&m); 15 int tr=0,tc=0; 16 for(int i=1; i<=m; i++) 17 { 18 int r,c; 19 scanf("%d%d",&r,&c); 20 if(!nr[r]) 21 { 22 tr++; 23 nr[r]++; 24 } 25 if(!nc[c]) 26 { 27 tc++; 28 nc[c]++; 29 } 30 } 31 dp[n][n]=0; 32 for(int i=n; i>=0; i--) 33 { 34 for(int j=n; j>=0; j--) 35 { 36 if(i!=n||j!=n) 37 dp[i][j]=(double)((n-i)*j*dp[i+1][j]+i*(n-j)*dp[i][j+1]+(n-i)*(n-j)*dp[i+1][j+1]+n*n)/(n*n-i*j); 38 } 39 } 40 printf("%.10lf ",dp[tr][tc]); 41 return 0; 42 }