打气球#
描述#
周末何老板到磁器口游玩。街边有小贩在组织一种打气球游戏，何老板很感兴趣。
店家立了一块布，布上画了 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 列的期望花费
每次选坐标有以下四种情况
- 不影响打掉的行列数量
- 增加一个打掉的行
- 增加一个打掉的列
- 同时增加打掉的行列各一个
对应的期望分别为
- $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}$
所以
边界：
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;
}