本文主要是介绍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;
}
这篇关于Codeforces 398B Painting The Wall(dp)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
