BZOJ4832: [Lydsy1704月赛]抵制克苏恩【期望DP】

4832: [Lydsy1704月赛]抵制克苏恩

【题目描述】

传送门

【题解】

期望DP就可以了,f[t][i][j][k]表示第t次攻击,有i个一血,j个二血,k个三血的仆从。
注意:血量可以小于0。

代码如下

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int T,K,A,B,C;double Ans,f[55][10][10][10];
int main(){
    for(scanf("%d",&T);T;T--){
        memset(f,0,sizeof(f));
        scanf("%d%d%d%d",&K,&A,&B,&C);
        f[0][A][B][C]=1;Ans=0;
        for(int t=0;t<K;t++)
        for(int i=0;i<=7;i++)
        for(int j=0;j<=7-i;j++)
        for(int k=0;k<=7-i-j;k++){
            Ans+=f[t][i][j][k]/(i+j+k+1);
            if(i>0) f[t+1][i-1][j][k]+=f[t][i][j][k]*(double)i/(i+j+k+1);
            if(j>0) f[t+1][i+1][j-1][min(k+1,7-i-j)]+=f[t][i][j][k]*(double)j/(i+j+k+1);
            if(k>0) f[t+1][i][j+1][min(k,6-i-j)]+=f[t][i][j][k]*(double)k/(i+j+k+1);
            f[t+1][i][j][k]+=f[t][i][j][k]/(i+j+k+1);
        }
        printf("%.2lf\n",Ans);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部