题解：AT_abc470_e [ABC470E] Concentration

· · 题解

首先，我们要明确，因为所有牌都是平等的（在游戏中，它们上面的数字不影响游戏过程），所以我们不关心牌上的数字，转而关心牌上的所有数字之和。

那事情就简单了。我们发现目前实际上有用的变量只有以下三个：

  1. 目前的血量
  2. 目前还有几种不知道任何信息的牌
  3. 目前还有几种知道了一张的位置的牌（2 和 3 可以表示出已经成功翻出的牌的数量，因为高桥按最优策略，所以两张都知道的牌会马上被翻出来）

因为数据范围小，我们直接 dp_{i,j,k} 表示出现这种情况的概率，最后再钦定只有没血（或者翻完了牌）才能对答案造成贡献即可。具体的转移可以看注释。时间复杂度 O(n^2m)。

:::success[Code]

#include<bits/stdc++.h>
using namespace std;
constexpr int maxn=1010101;
int a[201];
double dp[201][201][201];
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);
    int n,m;cin>>n>>m;
    int sum=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sum+=a[i];
    }
    //takahashi 的最优策略显然是每次新翻开两张，然后尽可能根据得到的信息匹配
    //于是我们可以拆贡献（因为所有牌是平等的）
    //然后我们令 dp[i][j][k] 表示还有 i 滴血，还有 j 种牌完全不知道信息，k 种牌知道一张的概率
    //然后我们显然等到血为 0 的时候就可以计算贡献了（当然，j=k=0 也可以）
    dp[m][n][0]=1;
    for(int i=m;i;i--)for(int j=n;~j;j--)for(int k=n-j;~k;k--){
        //从 dp[i][j][k] 往后面转移
        //如果他第一次抽到了完全不知道信息的牌，他只能瞎蒙，并且有 1/(2*j-1+k) 的概率撞到大运，变成 j-1,k
        //剩下来的概率会 -1 血，同时有 k/(2*j-1) 的概率得到一种已知一张的另一张，直接 j-1,k
        //注意要特判 i=1 的时候，此时认为他什么也没得到
        //剩下来的概率是得到另一张完全不知道的牌，变成 j-1,k+2
        if(j){
            dp[i][j-1][k]+=(j*2.0/(j*2+k))*(1.0/(j*2-1+k))*dp[i][j][k];//撞大运
            if(i>1)
                dp[i-1][j-1][k]+=(j*2.0/(j*2+k))*((k)*1.0/(j*2-1+k))*dp[i][j][k],
                dp[i-1][j-2][k+2]+=(j*2.0/(j*2+k))*((j*2-2)*1.0/(j*2-1+k))*dp[i][j][k];
            else
                dp[0][j][k]+=(j*2.0/(j*2+k))*((j*2-2+k)*1.0/(j*2-1+k))*dp[i][j][k];
                //这里不严谨，但是考虑到我们计入答案的只有 j+k 的值，所以这样写
        }
        //如果抽到了已知信息的牌，就可以直接令 k-1，变为 j,k-1
        if(k){
            dp[i][j][k-1]+=k*1.0/(j*2+k)*dp[i][j][k];
        }
    }
    double ans=0;
    //把牌抽完了
    for(int i=1;i<=m;i++){
        ans+=sum*dp[i][0][0];
    }
    //人没了
    for(int j=0;j<=n;j++)for(int k=0;k<=n-j;k++)
        ans+=sum*(n-j-k)*1.0/n*dp[0][j][k];
    printf("%.12lf",ans);
    return 0;
}

:::