Sorry, your browser cannot access this site
This page requires browser support (enable) JavaScript
Learn more >

打气球

描述

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

店家立了一块布,布上画了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

5 2 
2 3 
4 1

輸出範例 1

11.77

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

思路

这小贩真坑!

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

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

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

对应的期望分别为

  1. f(i,j)(ni)(nj)n2f(i,j)\cdot \frac{(n-i)\cdot (n-j)}{n^2}
  2. f(i,j1)(ni)jn2f(i,j-1)\cdot \frac{(n-i)\cdot j}{n^2}
  3. f(i1,j)i(nj)n2f(i-1,j)\cdot \frac{i\cdot (n-j)}{n^2}
  4. f(i1,j1)ijn2f(i-1,j-1)\cdot \frac{ij}{n^2}

所以

f(i,j)=f(i,j)(ni)(nj)n2+f(i,j1)(ni)jn2+f(i1,j)i(nj)n2+f(i1,j1)ijn2+1f(i,j)[1(ni)(nj)n2]=f(i,j1)(ni)jn2+f(i1,j)i(nj)n2+f(i1,j1)ijn2+1f(i,j)[n2(ni)(nj)]=f(i,j1)(ni)j+f(i1,j)i(nj)+f(i1,j1)ij+n2f(i,j)=f(i,j1)(ni)j+f(i1,j)i(nj)+f(i1,j1)ij+n2n2(ni)(nj)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)}

边界:

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

#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;
}

评论