题目链接: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 - 1107B. Digital root & 1107C. Brutality(规律 & 贪心)Codeforces - 1107B.
codeforces每日一练。 题意: 给一棵树,每个点有一个点权,每条边有一个边权,求一条链使得点权和-边权和最大。 思路: 由于我没看清楚题意,以为是求联通子图的点权和-边权和最大,用link-cut-tree写换根,wa10了两...
Codeforces 题库 101-200 共~500题 codeforces.com版权所有。 程序可提交至该网站评测。
Codeforces 1105B - Zuhair and Strings 测试点37个(全)
Codeforces 题库 001-100 共~500题 codeforces.com版权所有。 程序可提交至该网站评测。
codeforces编程网站预测分数插件
使用于Google Chrome的Codeforces Enhancer 1.1.2插件安装包。 版本:codeforces enhancer 1.1.2 使用浏览器:Google Chrome
题目分析:最优性问题,且是对区间操作的,而且数据范围满足 n^3 的时间复杂度,综上可以考虑区间dp,因为题目已经明确了需要求什么,所以我们不妨设 dp[ i ][ j ] 为区间 [ i , j ] 合并后的最短数列的长度,因为...
Some of the Codeforces problems codes
Codeforces 185A - Plant 全测试点49个
codeforces 19 E Fairy 一道比较难的题目的解题报告 推荐阅读
Codeforces global round 10 codes
Codeforces round 678 division 2 codes
lucifer1004大佬的博客cf上分攻略故里大佬的githubcf思维题刷题数:44- (1421)codeforces 676 div2 A,B done
Codeforces round 678 D2_Codeforces_源码
打codeforces的神器
codeforces-js Codeforces JS
使用 C# + WPF 开发 --- 还在发愁打了那么多场比赛都没有进入首页么? 还在为了前 5 的 hacker 名额阅读千份代码么? 是的,你没有看错! 这是一个 Edu & Div.3 轮 Open hacking 错误代码自动查找器!...
Codeforces Round #723 (Div. 2).md
Codeforces 题库 201-294 共~500题 codeforces.com版权所有。 程序可提交至该网站评测。