LibreOJ 2112 「HNOI2015」亚瑟王

一道有思维难度的期望 DP。
根据期望的线性性，可以算出每张牌发动的概率然后乘伤害最后加起来。

设 fi 表示第 i 张牌发动的概率。
首先有 f1=(1−(1−p1)r)。

我们发现一张牌发动的概率跟之前已经发动了几张牌有关。
所以可以设 gi,j 表示前 i 张牌，总共发动了 j 张（第 i 张不一定发动）。

转移，只需要考虑第 i 张牌是否发动即可。
有 fi,j=(1−(1−ai)r−j+1)fi−1,j−1+(1−ai)r−jfi−1,j

第一项对应发动，第二项对应不发动。

然后要预处理所有 (1−ai)j，并且特判 r=0 的情况。

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 220;
const int R = 132;
int T,n,r,d[N + 5];
double a[N + 5],f[N + 5],g[N + 5][R + 5],pw[N + 5][R + 5];
double ans;
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        ans = 0;
        scanf("%d%d",&n,&r);
        for(register int i = 1;i <= n;++i)
        {
            scanf("%lf%d",a + i,d + i),pw[i][0] = 1;
            for(register int j = 1;j <= r;++j)
                pw[i][j] = pw[i][j - 1] * (1 - a[i]);
        }
        if(!r)
        {
            puts("0");
            continue;
        }
        g[1][0] = pw[1][r],g[1][1] = f[1] = 1 - pw[1][r];
        for(register int i = 2;i <= n;++i)
            for(register int j = 0;j <= min(i,r);++j)
                g[i][j] = (j ? (1 - pw[i][r - j + 1]) * g[i - 1][j - 1] : 0) + (i ^ j ? pw[i][r - j] * g[i - 1][j] : 0);
        for(register int i = 2;i <= n;++i)
        {
            f[i] = 0;
            for(register int j = 0;j <= min(i - 1,r);++j)
                f[i] += g[i - 1][j] * (1 - pw[i][r - j]);
        }
        for(register int i = 1;i <= n;++i)
            ans += f[i] * d[i];
        printf("%.10f\n",ans);
    }
}