题目概述

刚开始有 $A$ 个一点血的奴隶主，$B$ 个两点血的奴隶主，$C$ 个三点血的奴隶主。有一个克苏恩要攻击 $K$ 次，每次攻击随机攻击奴隶主或者玩家。奴隶主被攻击之后没死并且现在的奴隶主数量没有超过 $6$ 就会产生一个新的三点血的奴隶主，问克苏恩期望打玩家多少血。

解题报告

很明显期望DP……我硬是写了半天才写出来……期望DP关键是要反着来。定义 $f_{i,a,b,c}$ 表示还剩下 $i$ 次攻击，目前一血二血三血的奴隶主有 $a,b,c$ 个，然后就是从 $f_{i-1}$ 转移过来。

示例程序

#include<cstdio>
#include<cstring>
using namespace std;
typedef long double DB;
const int maxn=50,maxa=7;

int te,n,A,B,C;DB f[maxn+5][maxa+5][maxa+5][maxa+5];

int main(){
    freopen("cthun.in","r",stdin);freopen("cthun.out","w",stdout);
    for (scanf("%d",&te);te;te--){
        scanf("%d%d%d%d",&n,&A,&B,&C);memset(f,0,sizeof(f));double ans=0;
        for (int i=1;i<=n;i++)
            for (int a=0;a<=maxa;a++)
                for (int b=0;b<=maxa;b++)
                    for (int c=0;c<=maxa;c++)
                        if (a+b+c<=maxa){
                            if (a) f[i][a][b][c]+=f[i-1][a-1][b][c]*a/(a+b+c+1);
                            if (b) f[i][a][b][c]+=f[i-1][a+1][b-1][c+(a+b+c<maxa)]*b/(a+b+c+1);
                            if (c) f[i][a][b][c]+=f[i-1][a][b+1][c-(a+b+c==maxa)]*c/(a+b+c+1);
                            f[i][a][b][c]+=(f[i-1][a][b][c]+1)/(a+b+c+1);
                        }
        printf("%.2f\n",(double)f[n][A][B][C]);
    }return 0;
}