D - Domination ZOJ - 概率DP

• D - Domination

•  ZOJ - 3822 
• 题意：给定一个N∗M的棋盘，每次任选一个位置放置一枚棋子，直到每行每列上都至少有一枚棋子，问放置棋子个数的期望。
• 思路：
• 注意天数k必须从至少得比max(i,j)大才有可能出现当前的状态
• dp[i][j][k+1]+=dp[i][j][k]∗(n−k)/(S−k)没有新的行列出现只能从当前行列中选取新点（要出去原来的的点）
• dp[i+1][j][k+1]+=dp[i][j][k]∗(N−i)∗j/(S−k)出现新的行但没有出现新的列所以可选的点为（n-i）*j
• dp[i][j+1][k+1]+=dp[i][j][k]∗(M−j)∗i/(S−k)出现新的列但没有出现新的行所以可选的点为（m-j）*i
• dp[i+1][j+1][k+1]+=dp[i][j][k]∗(N−i)∗(M−j)/(S−k)出现新的列也出现新的行所以可选的点为（m-j）*（n-i）.
• 概率算完了最后求期望 ，能够合法状态的期望但是每个dp里面存了这种状态出现的概率但是一旦有效之后放的就没有用了
• 所以相邻天数做差之后*天数求和就是期望值。

• #include<stdio.h>
  #include<cstring>
  #include<iostream>
  using namespace std;
  #define maxn 55
  int n,m,s,sp,t;
  double dp[maxn][maxn][maxn*maxn];
  int main()
  {
      scanf("%d",&t);
      while(t--)
      {
          double ans=0;
          scanf("%d%d",&n,&m);
          memset(dp,0,sizeof(dp));
          dp[1][1][1]=1;
          s=n*m;
          for(int i=1; i<=n; i++)
              for(int j=1; j<=m; j++)
              {
                  sp=i*j;
                  for(int k=max(i,j); k<=sp; k++)
                  {
                      dp[i][j][k+1]+=dp[i][j][k]*(sp-k)/(s-k);
                      dp[i+1][j][k+1]+=dp[i][j][k]*(n-i)*j/(s-k);
                      dp[i][j+1][k+1]+=dp[i][j][k]*(m-j)*i/(s-k);
                      dp[i+1][j+1][k+1]+=dp[i][j][k]*(n-i)*(m-j)/(s-k);
                  }
              }
          for(int i=max(n,m); i<=m*n; i++)
              ans+=(dp[n][m][i]-dp[n][m][i-1])*i;
          printf("%.9lf\n",ans);
      }
      return 0;
  }