首页 > 代码库 > codeforces D. Painting The Wall

codeforces D. Painting The Wall

2024-11-21 22:44:02   203人阅读

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\n",dp[tr][tc]);41     return 0;42 }
View Code

 

codeforces D. Painting The Wall


联系
我们