题解：AT_abc470_e [ABC470E] Concentration

· · 题解

这好像是我第一次 abc 在场上没有过 E？（思路是对的，但是代码半天调不过。）

思路

先考虑什么样的策略才是最优的。

将场上的牌分为两类：已知数字的和未知数字的。对于已知数字的牌，其中一定没有两张相同数字的，因为相同数字的牌可以提前消掉，获得价值并且不消耗生命值。

然后考虑每一次如何选牌：第一张一定选未知数字的，这样第二张就可以根据第一张的结果来选择。如果第一张选的数字出现在了已知牌中，就将它们配对，这一轮就结束了；如果第一张选的数字没有出现过，就只能再抽一张未知牌，这样会有三种情况：

  1. 第一张和第二张数字相同，可以直接消去。
  2. 第二张和已知数字的某一张牌数字相同，那这一轮仍然是匹配失败的，但是下一轮（如果还有生命值的话）就可以将这两张牌匹配，以保证已知牌中没有相同数字的。
  3. 第二张和前面的牌数字都不同，那没办法，只能继续选。

这就是最优策略了。但是还剩下一个问题：不同牌的价值不同，如何计算价值呢？容易发现上面的决策不受牌价值的影响，都是能匹配就尽量匹配（反正匹配成功不需要代价），而第一次摸到什么数字是随机的，因此可以将每次的价值都视为任选一张牌的期望价值，即 \frac{\sum_{i=1}^n A_i}{n}。

理清楚思路后，代码实现就很好想了（然而并不好写！）。设 f[i][j][k] 表示从有 i 张未知牌，j 张已知牌，剩k 点生命值的情况操作到游戏结束的期望分数，初始状态为 f[N*2][0][L]，按上述策略转移即可。实际写代码时，写成记忆化搜索的形式比较方便，不用考虑太多的边界条件。

时空复杂度都为 O(N^2L)，细节请看代码和注释。

代码

#include <bits/stdc++.h>
using namespace std;
const int N=205;

int n,m;
double v,f[N*2][N][N];//f[i][j][k]：有i张不确定，j张确定，生命为k的最大得分期望

double dfs(int x,int y,int z)
{
    if(x<=0||y<0||z<=0||y>n)//边界
        return 0;
    if(f[x][y][z]!=-1)//记忆化
        return f[x][y][z];
    f[x][y][z]=0;
    double p=1.0*y/x;//p 表示第一次抽取的数字在已知数字中的概率
        f[x][y][z]=p*(dfs(x-1,y-1,z)+v);//第一次抽到已知数字
    if(x>1)//再判一次边界，防止除以 0 或通过非法情况加上 v
    {
        f[x][y][z]+=(1-p)*1.0/(x-1)*(dfs(x-2,y,z)+v);//两次抽到的数字相同
        if(z>1)//如果这次扣完血直接死了，就不能再匹配了
            f[x][y][z]+=(1-p)*1.0*y/(x-1)*(dfs(x-2,y,z-1)+v);//第二次抽到已知数字
        f[x][y][z]+=(1-p)*(1-1.0*(y+1)/(x-1))*dfs(x-2,y+2,z-1);//都没有重复的
    }
    return f[x][y][z];
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        int x;
        scanf("%d",&x);
        v+=x;
    }
    v/=n;//计算期望得分
    for(int i=0;i<N*2;i++)
        for(int j=0;j<N;j++)
            for(int k=0;k<N;k++)
                f[i][j][k]=-1;
    printf("%.10lf",dfs(n*2,0,m));
    return 0;
}