首页 > 代码库 > ZOJ 3822 Domination

ZOJ 3822 Domination

dp :

 

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAX = 51;
double dp[MAX*MAX][MAX][MAX];
int main() {
    int cas;
    int n,m;
    scanf("%d",&cas);
    while(cas--) {
        scanf("%d %d",&n,&m);
        memset(dp,0,sizeof(dp));
        dp[0][0][0]=1.0;
        double tot=n*m,res=0;
        for(int i=1;i<=(n*m)-min(n,m)+1;i++) {
            for(int j=1;j<=n;j++) {
                for(int k=1;k<=m;k++) {
                    if(tot-i+1>0&&(n-(j-1))>0)
                    dp[i][j][k]+=dp[i-1][j-1][k]*(double)((n-(j-1))*k)/(double)(tot-i+1);
                    if(tot-i+1>0&&(m-k+1)>0)
                    dp[i][j][k]+=dp[i-1][j][k-1]*(double)(j*(m-k+1))/(double)(tot-i+1);
                    if((n-j+1)>0&&(m-k+1)>0&&(tot-i+1)>0)
                    dp[i][j][k]+=dp[i-1][j-1][k-1]*(double)((n-j+1)*(m-k+1))/(double)(tot-i+1);
                    if((tot-i+1)>0&&j*k-i+1>0)
                    dp[i][j][k]+=dp[i-1][j][k]*(double)(j*k-i+1)/(double)(tot-i+1);
                }
            }
           // if(dp[i][n][m]!=0) printf("%d\n",i);
            res+=(dp[i][n][m]-dp[i-1][n][m])*i;
        }
        printf("%.12lf\n",res);
    }
    return 0;

} 

ZOJ 3822 Domination