打气球

描述

周末何老板到磁器口游玩。街边有小贩在组织一种打气球游戏，何老板很感兴趣。

店家立了一块布，布上画了N*N的方格，有的方格里挂上了气球，有的没有。

游戏规则如下：

第1步.观察。如果每一行都至少有一个方格没有气球，并且每一列都至少有一个方格没有气球，游戏结束。否则进行第2步。

第2步.抛骰子。店家拿出一个特制的骰子，该骰子有N个面，上面依次有1到N这N 个数字。玩家先后抛两次骰子，设第一次抛出的数字为x，设第二次抛出的数字为y (注：抛出的数字是随机的)。

第3步.打气球。若坐标为(x,y)的格子里有气球，玩家必须将其打爆。子弹1块钱一发。

如果该格子没有气球，忽略该格子，玩家不用开枪，但玩家也需要支付给店家1块钱。

第4步.继续。执行第1步。

何老板是个神枪手，他能做到百发百中。他想你帮他算算，对于当前给出的这局游戏，预计要花多少钱才能结束。

輸入

第一行，两个整数N和M，N表示方格的尺寸,M表示游戏开始时，有M个格子里是没有气球的。 接下来M行，每行两个整数x,y,表示坐标为x,y的格子里没有气球。

輸出

一行，一个实数，完成游戏预计花费，保留2个小数位。

輸入範例 1

1
2
3

5 2 
2 3 
4 1

輸出範例 1

1

11.77

更多样例请点击wyx大佬的博客

思路

这小贩真坑！

设f[i][j]表示消掉i行j列的期望花费

每次选坐标有以下四种情况

1. 不影响打掉的行列数量
2. 增加一个打掉的行
3. 增加一个打掉的列
4. 同时增加打掉的行列各一个

对应的期望分别为

1. $f(i,j)\cdot \frac{(n-i)\cdot (n-j)}{n^2}$
2. $f(i,j-1)\cdot \frac{(n-i)\cdot j}{n^2}$
3. $f(i-1,j)\cdot \frac{i\cdot (n-j)}{n^2}$
4. $f(i-1,j-1)\cdot \frac{ij}{n^2}$

所以
$$
f(i,j)=f(i,j)\cdot \frac{(n-i)\cdot (n-j)}{n^2}+f(i,j-1)\cdot \frac{(n-i)\cdot j}{n^2}+f(i-1,j)\cdot \frac{i\cdot (n-j)}{n^2}+f(i-1,j-1)\cdot \frac{ij}{n^2}+1\
f(i,j)[1-\frac{(n-i)(n-j)}{n^2}]=f(i,j-1)\cdot \frac{(n-i)\cdot j}{n^2}+f(i-1,j)\cdot \frac{i\cdot (n-j)}{n^2}+f(i-1,j-1)\cdot \frac{ij}{n^2}+1\
f(i,j)[n^2-(n-i)(n-j)]=f(i,j-1)\cdot (n-i)\cdot j+f(i-1,j)\cdot i\cdot (n-j)+f(i-1,j-1)\cdot ij+n^2\
f(i,j)=\frac{f(i,j-1)\cdot (n-i)\cdot j+f(i-1,j)\cdot i\cdot (n-j)+f(i-1,j-1)\cdot ij+n^2}{n^2-(n-i)(n-j)}
$$
边界：

1
2
3
4
5

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

要死了噗

重点要注意的是输入的是没有气球的格子

我和hqx大佬被坑了好久嘤

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

#include<cstdio> 
#include<iostream>
using namespace std;

const int MAXN=2000+5;

int hang[MAXN],lie[MAXN];
double f[MAXN][MAXN];



int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i){
		int x,y;
		scanf("%d%d",&x,&y);
		hang[x]=1;
		lie[y]=1;
	}
	int h=n,l=n;
	for(int i=1;i<=n;++i){
		if(hang[i])--h;
		if(lie[i])--l;
	}
	f[0][0]=0;
	for(int i=1;i<=n;++i){
		f[0][i]=f[0][i-1]+1.0*n/i;
		f[i][0]=f[i-1][0]+1.0*n/i;
	}
	for(int i=1;i<=h;++i){
		for(int j=1;j<=l;++j){
//			f[i][j]=f[i-1][j]*1.0*i*(n-j)/n/n+f[i][j-1]*1.0*(n-i)*j/n/n+f[i-1][j-1]*1.0*i*j/n/n+f[i][j]*1.0*(n-i)*(n-j)/n/n+1;
			f[i][j]=1.0*(f[i-1][j]*i*(n-j)+f[i][j-1]*(n-i)*j+f[i-1][j-1]*i*j+n*n)/(n*n-(n-i)*(n-j));
		}
	}
	printf("%.2lf\n",f[h][l]);
	return 0;
}