P3239 [HNOI2015]亚瑟王

· · 题解

发一个不一样的做法。

我目前没有找到一样的解法，大家都是概率期望两步走，而此做法并不是。

做法来源于我的一个朋友：_Veritas

我让他发个题解，他虽然答应了，但是由于已经开学，可能会鸽一会，所以我先发一篇，等他发了推荐大家去看原创。

原创链接：暂无

题意简述：

有 n 张卡牌，玩 r 轮游戏。每轮游戏从左向右轮流考虑每张没有发动 过的卡牌，考虑到第 i 张卡时，它有 p_i 的概率发动并产生 d_i 的贡献， 然后本轮立即结束并进入下一轮。若没有卡牌发动则直接进入下一轮。

$T ≤ 444, n ≤ 220, r ≤ 132

分析:

一个比较不好处理的条件就是如果触发一次攻击，马上会重新开始一轮。

考虑转化问题，原问题可以转化为：一次性地从第1张牌到第n张牌依次考虑，每一张牌有一定的概率被触发攻击（注意此概率并非原题中的p[i]），总共有r次触发的机会，每触发一次，剩余可以触发的次数就会减少一次，如：第一次触发，那么剩下的机会就变成r-1。

如此，问题就转化成了序列上的概率期望dp问题，设dp[i][j]表示前1-i张牌，还有j次触发攻击的机会没有使用的情况对答案的贡献，要倒着推，所以最终答案就是dp[1][r]。

状态转移：

dp[i][j]=dp[i+1][j]*(1-p[i])^{j}+(dp[i+1][j-1]+d[i])*(1-(1-p[i])^{j})

解释一下：考虑到第i张牌,还有j次触发的机会，此状态下有两种可能:第一种可能是第i张牌没有触发，发生概率是(1-p[i])^j，其指向情况是dp[i+1][j]；第二种可能是第i张牌触发了，用掉一次机会，概率显然是1-(1-p[i])^j，其指向的情况是dp[i+1][j-1]。这就解释完了。

如果把状态转移看成一个有向无环图的话，上文中的“其指向的情况”其实就是一条有向边，如果知道绿豆蛙的归宿为什么要反向建边，就同样可以理解为什么要倒推。

再多说一点，绿豆蛙的归宿也可以不反向建边，那就要概率期望两步走。而此题几乎所有人的做法都是正着推，其实就是概率期望两步走，类似于绿豆蛙的归宿那道题正着建图的做法。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int T,n,r;
double p[222],d[222],dp[222][150];
double Pow(double a, int m)
{
    double base=a, res=1;
    while(m>0)
    {
        if(m&1) res*=base;
        base*=base, m>>=1;
    }
    return res;
}
int main()
{
    cin>>T;
    while(T--)
    {
        memset(dp,0,sizeof(dp));
        cin>>n>>r;
        for(int i=1;i<=n;++i) cin>>p[i]>>d[i];
        for(int i=n;i>0;--i)
        {
            for(int j=1;j<=r;++j)
            {
                double P=Pow(1.0-p[i],j);
                dp[i][j]=dp[i+1][j]*P+(dp[i+1][j-1]+d[i])*(1.0-P);
            }
        }
        printf("%.10lf\n", dp[1][r]);
    }
    return 0;
}