Luogu8213 挑战 | Arahc's Home

题面

简化题意

两个人玩一个博弈，每人每轮可以选择把棋子向前移不超过 $p_i$ 格，然后选择是否发起一次挑战，挑战结果是根据所在格子的两个参数 $p_i,q_i$ 随机产生的。根据挑战结果会发生下面事情之一：

什么都不会发生。
这个人再次行动一轮。
这个人的下一轮行动被跳过。

求两人都用最优策略时先手的胜率，误差不超过 $10^{-6}$ 。

$n\leq 10^5,p_i,q_i\leq 333$ 。

题解

本来一看到博弈论+概率以为是线性规划啥的，结果是个动态规划的诈骗题。因为本质是诈骗所以题目不算难，题解还是写得清楚一点好，老少皆宜。

考虑自己能否选择挑战的情况：要么可以挑战；要么不能发起挑战；要么就是别人给我送了一轮，则我连续操作两次，根据题意，第一次不能挑战，第二次能挑战。

注意：这里的“可以挑战”不代表“必须挑战”。

于是设一个这样的状态： $f_{i,0/1/2}$ 表示棋子在第 $i$ 格，目前接手的这个人（有代入感地假设是自己）能否挑战的情况为上述三种里的哪一种（ $0/1/2$ 依次对应上面说的三种情况），此时这个人的胜率。

发现这样转移大概是 $\mathcal O(np)$ 的还带 $3$ 的常数所以刚好卡在了 $10^8$ 线……

估计完复杂度了，来看怎么转移。倒序枚举 $i$ 。先考虑不能挑战的情况，只能向前移动棋子，此时我的最大胜率就应该是对方的最大败率，即：

f_{i,1} \gets \max_j^{p_i} (1-f_{i+j,0})

其中 $j$ 枚举的是我移动多少步，后文和代码的 $j$ 都是这个含义。

然后是第一步不能挑战，然后能挑战的情况，也比较显然（转移方程就是这句话的字面意思）：

f_{i,2} \gets \max_j^{p_i} (f_{i+j,0})

最后看看能挑战吧 =.=，显然能挑战并不代表必须挑战，此时 $f_{i,0}$ 和 $f_{i,1}$ 一样，重点是挑战的情况（这里说的“贡献”指的是对我的胜率的贡献）：

挑战成功，下一步继续移动，但不能挑战，产生的贡献是下一步移动的胜率（即 $f_{i+j,1}$ ）乘上挑战成功的概率。
挑战平局，下一步是对方，贡献是对方的败率（即 $1-f_{i+j,0}$ ）乘上挑战平局概率。
挑战失败，白给对方一步，贡献是对方连走两步的败率（即 $1-f_{i+j,2}$ ）乘上挑战失败的概率。

于是思路很清晰了，考虑成功、平局、失败的概率，因为三者加起来是 $1$ ，我们就只算前两个吧。

直接用成功/平局的结局数除以总的结局数 $n\times(m+1)$ 即可，两种情况的结局数如下：

成功：钦定挑战能量，则活化能可以是小于挑战能量的任何数，根据 $n$ 是否不超过 $m$ 分类讨论即可。
平局：二者必须相同，显然方案数为 $\min(n,m)$ 。

具体还可以看代码理解。

到这里所有的问题都已经解决了，复杂度是 $\mathcal O(np)$ ，带有约为 $3$ 的常数因子。可以通过本题。

代码

注意一些小细节即可，比如 $j=p_i$ 的时候是不能挑战的，等等。

#include<bits/stdc++.h>
using namespace std;
const int max_n=100005;
inline int read(){
    int x=0;bool w=0;char c=getchar();
    while(c<'0' || c>'9') w|=c=='-',c=getchar();
    while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return w?-x:x;
}
inline void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10^48);
}

double f[max_n][3];
int n,p[max_n],q[max_n];

inline double P(int n,int m){ // 成功概率
    if(n<=m) return (n+1)/2.0/(m+1);
    return (2*n-m)/2.0/n;
}
inline double Q(int n,int m){ // 平局概率
    return min(n,m)*1.0/n/(m+1);
}
inline double R(int n,int m){ // 失败概率
    return 1-P(n,m)-Q(n,m);
}

signed main(){
    n=read();
    for(register int i=0;i<n;++i)
        p[i]=read();
    for(register int i=0;i<n;++i)
        q[i]=read();
    for(register int i=n-1;i>=0;--i){
        for(register int j=1,up=min(p[i],n-i);j<=up;++j){
            f[i][1]=max(f[i][1],1-f[i+j][0]),
            f[i][2]=max(f[i][2],f[i+j][0]);
            if(j!=p[i])
                f[i][0]=max(f[i][0],max(f[i][1],f[i+j][1]*P(p[i]-j,q[i]+q[i+j])+(1-f[i+j][0])*Q(p[i]-j,q[i]+q[i+j])+(1-f[i+j][2])*R(p[i]-j,q[i]+q[i+j])));
            else
                f[i][0]=max(f[i][0],f[i][1]);
        }
    }
    printf("%.10lf",f[0][0]);
    return 0;
}