打气球

描述

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

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

边界:

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