ZOJ 3822 可能性DP

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3822

本场比赛之前，我记得。见WALK概率路DP称号。那么它应该是可以考虑的概率DP，十一还特意看了碍着，

当场景。真的OUT了。然后好激动的样子，開始推得二维。然后感觉好难推。发现n仅仅有50。所以就去推三维，然后发现k<max(i,j)的时候，有无用状态，无用状态初始化不会处理，然后认为好像也用不到，可是感觉更稳的还是去推二维，然后就陷入二维--------悲剧了最后打铁，真他妈不爽

也发现了自己的问题：1、平时学的东西掌握的不够扎实

2、事实上假设队友没明确自己的意思，全然自己推吧，自信点，别想着必须队友确认才去做

想要保研牛校或者出国。单单小的竞赛还是不够的，ACM假设不出结果会有非常大压力。预计保牛校无望，我校牛逼的学长学姐。也就是清华或者交大的硕博连读或者博士，这对于92年出生的我实在不能忍......

还有西安一站，这几天我会全力最后一搏，下次比赛绝不犯此次比赛的错误。假设自己的思路队友这边难以沟通，必要的话，就自己坚持自己想自己做，尤其自信点，有非常多人事实上不像他们想象的那样强，我自己也不想我想的那么弱

E[i][j][k] 已经占领i行j列。走了k步的时候，还须要走的步数的期望。其它看代码就好

#include <cstdio>

#include <cstring>

#include <iostream>

using namespace std;

#define CL(a,b) memset(a,b,sizeof(a))

#define IN(s) freopen(s,"r",stdin)

const int MAXN = 55;

double dp[MAXN][MAXN][MAXN*MAXN];

int main()

{

    //IN("D.txt");

    int ncase;

    scanf("%d",&ncase);

    int n,m;

    while(ncase--)

    {

        scanf("%d%d",&n,&m);

        CL(dp,0);

        for(int i=n;i>=0;i--)

            for(int j=m;j>=0;j--)

            {

                if(i==n&&j==m)continue;

                for(int k=i*j;k>=max(i,j);k--)

                {

                    dp[i][j][k]+=1.0*j*(n-i)/(1.0*n*m-k)*dp[i+1][j][k+1];

                    dp[i][j][k]+=1.0*i*(m-j)/(1.0*n*m-k)*dp[i][j+1][k+1];

                    dp[i][j][k]+=1.0*(i*j-k)/(1.0*n*m-k)*dp[i][j][k+1];

                    dp[i][j][k]+=1.0*(n-i)*(m-j)/(1.0*n*m-k)*dp[i+1][j+1][k+1];

                    dp[i][j][k]+=1.0;

                }

            }

        printf("%.12lf\n",dp[0][0][0]);

    }

    return 0;

}

秒客网

ZOJ 3822 可能性DP

相关文章