小 K 不慎被 LL 邪教洗脑了,洗脑程度深到他甚至想要从亚瑟王邪教中脱坑。他决定,在脱坑之前,最后再来打一盘亚瑟王。既然是最后一战,就一定要打得漂亮。众所周知,亚瑟王是一个看脸的游戏,技能的发动都是看概率的。

作为一个非洲人,同时作为一个前 OIer,小 K 自然是希望最大化造成伤害的期望值。但他已经多年没写过代码,连 Spaly都敲不对了,因此,希望你能帮帮小 K,让他感受一下当欧洲人是怎样的体验。
(即 ii 等于 nn),则结束这一轮;否则,考虑下一张卡牌。

请帮助小 K 求出这一套卡牌在一局游戏中能造成的伤害的期望值。

本题中我们将考虑游戏的一个简化版模型。 玩家有一套卡牌,共 n 张。游戏时,玩家将 n 张卡牌排列成某种顺序,排列后将卡牌按从前往后依次编号为 1 - n。本题中,顺序已经确定,即为输入的顺序。每张卡牌都有一个技能。第 i 张卡牌的技能发动概率为 pip_i ,如果成功发动,则会对敌方造成 did_i 点伤害。也只有通过发动技能,卡牌才能对敌方造成伤害。基于现实因素以及小 K 非洲血统的考虑,pip_i 不会为 0,也不会为 1,即 0<pi<10 < p_i < 1。 一局游戏一共有 r 轮。在每一轮中,系统将从第一张卡牌开始,按照顺序依次考虑每张卡牌。在一轮中,对于依次考虑的每一张卡牌:

  1. 如果这张卡牌在这一局游戏中已经发动过技能,则
    1.1. 如果这张卡牌不是最后一张,则跳过之(考虑下一张卡牌); 否则(是最后一张),结束这一轮游戏。

  2. 否则(这张卡牌在这一局游戏中没有发动过技能),设这张卡牌为第 i 张
    2.1. 将其以 pip_i 的概率发动技能。
    2.2. 如果技能发动,则对敌方造成 did_i 点伤害,并结束这一轮。
    2.3. 如果这张卡牌已经是最后一张

链接 🔗

「HNOI2015」亚瑟王

题解 ❓

dp[i][j]dp[i][j] 为前ii张牌,恰好有jj张在所有轮发动的概率

ii轮发动
dp[i][j]+=dp[i1][j1](1(1p[i])rj+1)(i>0)dp[i][j] += dp[i-1][j-1] * (1 - (1 - p[i])^{r-j+1}) (i > 0)
因为前面已经有(j1)(j-1)张牌发动了,所以该牌仅有可能有rj+1r-j+1次机会

ii轮不发动
dp[i][j]+=dp[i1][j]((1p[i])rj)(i!=j)dp[i][j] += dp[i-1][j] * ((1 - p[i])^{r-j}) (i!=j)
因为前面已经有jj张牌发动了,所以该牌仅有可能有rjr-j次机会

对于第i张牌在总局数中发动的g[i]g[i]概率为
g[i]=j=0(i1,r)(1(1p[i])rj)dp[i1][j]g[i] = \sum_{j=0}^(i-1,r) (1 - (1 - p[i])^{r-j}) dp[i-1][j]
dp[i1][j]dp[i-1][j] 表示前面选了jj张了,当前这张选中的概率为(1 - (1 - p[i])^{r-j})

代码

const int mod = 2e5+10;
const int N = 301;
ll a[N];
double dp[N][N],pw[N][N],p[N],g[N];
int main()
{
//    __IN;__OUT;
    ll t; RLL(t);
    while(t--)
    {
        MM(dp,0);MM(g,0);
        ll n,k;RLL2(n,k);
        FOR(i,1,n) RLF(p[i]),RLL(a[i]);
        if(k==0)
        {
            PS("0.0000000000");
            continue;
        }
        FOR(i,1,n) pw[i][0] = 1.0;
        // pw,第i张牌,抽j次抽不中的概率
        FOR(i,1,n) FOR(j,1,k) pw[i][j] = pw[i][j-1] * (1.0 - p[i]);
        dp[1][0] = pw[1][k]; dp[1][1] = g[1] = 1.0 - pw[1][k];
        FOR(i,2,n)
            FOR(j,0,min(i,k))
            {
                if(j) dp[i][j] += dp[i-1][j-1] * (1.0 - pw[i][k-j+1]);
                if(i != j) dp[i][j] += dp[i-1][j] * pw[i][k-j];
            }
        FOR(i,2,n) FOR(j,0,min(i-1,k)) g[i] += dp[i-1][j] * (1.0 - pw[i][k-j]);
        double res = 0.0;
        FOR(i,1,n) res += g[i] * a[i];
        printf("%.10lf\n",res);
    }
    return 0;
}