zoj 3822 Domination 概率dp

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int T;
int l,c;
double dp[2605][55][55];
bool b[2605][55][55];
double DP(int k,int x,int y){
    if(x>=l&&y>=c)return 0;
    if(b[k][x][y])return dp[k][x][y];
    if(x==0||y==0)return DP(k+1,x+1,y+1)+1;
    int st = x*y-k;int lst = l*c-k;int las = (l-x)*(c-y);
    double ans = 0;
    //if(lst==0)return 0;
    if(k<x*y)ans += DP(k+1,x,y)*(st/(1.0*lst));
    if(x<l)ans+=(l-x)*y/(1.0*lst)*DP(k+1,x+1,y);
    if(y<c)ans+=(c-y)*x/(1.0*lst)*DP(k+1,x,y+1);
    if(x<l&&y<c)ans+=las/(1.0*lst)*DP(k+1,x+1,y+1);
    b[k][x][y]=1;
    return dp[k][x][y] = ans+1;
}
int main(){
    scanf("%d",&T);
    while(T--){
        memset(dp,0,sizeof(dp));memset(b,0,sizeof(b));
        scanf("%d%d",&l,&c);
        printf("%.12lf\n",DP(0,0,0));
    }
}

zoj 3822 Domination 概率dp

原文：http://blog.csdn.net/ying_5/article/details/43310113