`
阿尔萨斯
  • 浏览: 4107586 次
社区版块
存档分类
最新评论

Codeforces 398B Painting The Wall(dp)

 
阅读更多

题目链接:Codeforces 398B Painting The Wall


题目大意:给出n和m,表示在一个n*n的平面上有n*n个瓷砖,其中有m块已经涂色。现在随机选中一块进行涂色(如果已经涂色跳过,也消耗时间),消耗1个步骤。终止条件为每行每列都有至少有一块瓷砖被涂色。问说涂成满意的情况需要时间的期望。


解题思路:现场出不来这道题,看来练的还是太少。题目可以理解成行涂n行,列涂n列。那么dp[i][j]表示行有i行还没有涂,列有j列还没涂的情况下需要的时间期望;然后对于每个涂完色的瓷砖,可以等价移动至右下角(只要保证行数和列数不变)。然后大致可以将图分成4分,如果选择左上角上的一块,那么行和列都将被涂上一个;右上角的话,行被涂上一个,列不变;左下角的话,行不变,列被涂上一个;右下角,行列都不变。

所以有dp[i][j] = 1(无论如何都要消耗时间) + k / (n^2);

k = i*j*dp[i-1][j-1] + (n-i)*j*dp[i][j-1] + i*(n-j)*dp[i-1][j] + (n-i)*(n-j)*dp[i][j];

注意等式右边也有未知数dp[i][j],要化简公式。


#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;
const int N = 2005;

int n, m, r, l, x[N], y[N];
double dp[N][N];

void init () {
	memset(x, 0, sizeof(x));
	memset(y, 0, sizeof(y));

	scanf("%d%d", &n, &m);
	int a, b;
	r = l = n;

	for (int i = 0; i < m; i++) {
		scanf("%d%d", &a, &b);
		if (x[a] == 0) r--;
		if (y[b] == 0) l--;
		x[a]++; y[b]++;
	}
}

double solve () {
	dp[0][0] = 0;

	for (int i = 1; i <= n; i++) {
		dp[i][0] = dp[i-1][0] + n*1.0/i;
		dp[0][i] = dp[0][i-1] + n*1.0/i;
	}

	for (int i = 1; i <= r; i++) {
		for (int j = 1; j <= l; j++) {
			dp[i][j] = n * n;
			dp[i][j] += i * j * dp[i-1][j-1];
			dp[i][j] += i * (n-j) * dp[i-1][j];
			dp[i][j] += (n-i) * j * dp[i][j-1];

			dp[i][j] /= (n*n - (n-i)*(n-j));
		}
	}
	return dp[r][l];
}

int main () {
	init ();
	printf("%.10lf\n", solve () );
	return 0;
}


分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics