ZOJ3822 ACM-ICPC 2014 亞洲區域賽牡丹江賽區現場賽D題Domination 概率DP（兩種解法）

ZOJ3822 ACM-ICPC 2014 亞洲區域賽牡丹江賽區現場賽D題Domination 概率DP（兩種解法）

題目地址：點擊打開鏈接

這道題有兩種做法，第一種是直接求期望，類似於poj 2096 區別在於這個步數有限。所以要迭代步數。

#include 
#include 
#include 
#define maxn 55//這裡剛開始寫成了50+10 那麼maxn*maxn就會小很多wa了一次
using namespace std;
double dp[maxn][maxn][maxn*maxn];
int N,M,T;
int main()
{
    while(~scanf("%d", &T))while(T--)
    {
        scanf("%d%d",&N,&M);
        memset(dp,0,sizeof(dp));
        for(int i=N;i>=0;i--)
            for(int j=M;j>=0;j--)
            {
                if(i==N && j==M) continue;//狀態定義:dp[i][j][k] 走了k步覆蓋了i行j列，此情況下能完全覆蓋的期望
                for(int k=i*j;k>=max(i,j);k--)//步數不可能比i*j更多也要大於i,j中最大值因為已經覆蓋了這麼些
                {
                    double p0=1.0*(i*j-k)/(N*M-k);
                    double p1=1.0*(M-j)*i/(N*M-k);
                    double p2=1.0*(N-i)*j/(N*M-k);
                    double p3=1.0*(N-i)*(M-j)/(N*M-k);
                    dp[i][j][k]=dp[i][j][k+1]*p0+dp[i][j+1][k+1]*p1+dp[i+1][j][k+1]*p2+dp[i+1][j+1][k+1]*p3+1;
                }
            }
        printf("%.12lf\n",dp[0][0][0]);
    }
    return 0;
}

第二種是求概率，完事以後再算期望。（若是對於不限步數的題目來說這個方法是不能用的）

#include
#include
#include
#include

using namespace std;
double dp[55][55][55*55];
const double eps=1e-8;

int main()
{
  //  freopen("in.txt","r",stdin);
    int t;
    cin>>t;
    while(t--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        memset(dp,0,sizeof(dp));
        memset(a,0,sizeof(a));
        dp[1][1][1]=1;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                if(i==n && j==m) break;
                for(int k=max(i,j);k<=i*j;k++)
                {
                    dp[i][j][k+1]+=dp[i][j][k]*(i*j-k)/(n*m-k);
                    dp[i+1][j][k+1]+=dp[i][j][k]*(n-i)*j/(n*m-k);
                    dp[i][j+1][k+1]+=dp[i][j][k]*(m-j)*i/(n*m-k);
                    dp[i+1][j+1][k+1]+=dp[i][j][k]*(n-i)*(m-j)/(n*m-k);
                }
            }
        }
        double sum=0;
        for(int i=max(n,m);i<=n*m;i++)
            sum+=dp[n][m][i]*i;
        printf("%.12f\n",sum);
    }
    return 0;
}