题解：AT_abc470_e [ABC470E] Concentration

· · 题解

前情提要

你做完了 ABCD。

你的 F 貌似很对但是错了。

啊怎么还有 15min。

终究还是要掉分了吗。
不，我的使命还没有结束！

思路

啊我做 F 之前看过 E 了。
是个期望 dp。

回顾一下，显然我们要根据目前的信息来进行推理。
显然我们要翻我们没翻过的。
我们已知的信息也就是那些我们翻过且没有匹配的牌。
我们还要知道有多少对我们丝毫不清楚，即多少对的两张牌我们都没有翻过。

此时我们可以设计一个 dp_{i,j,k} 表示有 i 个生命值，j 对我们丝毫不清楚的牌，k 张我们翻过而且没有匹配的牌。
显然我们没翻过的牌有 u=2j+k。

我们可以翻到与我们知道的且没有匹配的 k 张牌匹配。
不掉血，贡献为 1。
概率为 \frac{k}{u}。
我们失去了一张翻过且未匹配的牌。

然后就会有 \frac{2j}{u} 的概率没有出现。
对于下一个牌的情况进行分类讨论。

首先可以我们跟刚才的牌匹配，不掉血，贡献为 1，概率为 \frac{1}{u-1}，损失一对丝毫不清楚的牌，翻过但未匹配的牌不变。

还可以跟之前的牌匹配，掉 1 滴血，贡献为 1，概率为 \frac{k}{u-1}，损失一对丝毫不清楚的牌，翻过但未匹配的牌不变。

最后就是丝毫没有贡献，掉 1 滴血，贡献滚木，概率为 \frac{2(j-1)}{u-1}，损失两对丝毫不清楚的牌，翻过但未匹配的牌加二。

那么此时我们发现贡献其实贡献的一次加分操作，而不是直接的分数。
一次加分操作的期望加分就是 \frac{1}{n}\sum_{i=1}^n a_i，也就是平均值。

答案就是：

\frac{1}{n}dp_{l,n,0}\sum_{i=1}^n a_i 
#include <bits/stdc++.h>
#define SACRIFICING using
#define THE namespace
#define ROOK std
SACRIFICING THE ROOK;
typedef long long ll;
int n,l;
int a[209];
ll tot;
double dp[409][409][409];
int main(){
    cin>>n>>l;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        tot+=a[i];
    }
    l=min(l,n);
    for(int i=1;i<=l;i++){
        for(int k=0;k<=n;k++){
            dp[i][0][k]=k;
        }
        for(int j=1;j<=n;j++){
            for(int k=0;k<=n-j;k++){
                int u=2*j+k;
                double res=0;
                if(k>0){
                    res+=k*1.0/u*(1.0+dp[i][j][k-1]);               
                }
                double sd=(1.0/(u-1))*(1.0+dp[i][j-1][k]);
                if(i>1){
                    if(k>0){
                        sd+=(1.0*k/(u-1))*(1.0+dp[i-1][j-1][k]);
                    }
                    if(j>=2){
                        sd+=(1.0*(2*(j-1))/(u-1))*dp[i-1][j-2][k+2];
                    }
                }
                res+=2.0*j/u*sd;
                dp[i][j][k]=res;
            }
        }
    }
    cout<<fixed<< setprecision(10)<<dp[l][n][0]*1.0/n*tot<<'\n';
    return 0;
}

后记

不，我的使命……还没有结束！
离黄 perf 最近的一次。
离 AK 最近的一次。
我的 F 因为翻糖然后没了。
G 的 trick 是我们模拟赛的，但是我没看。

啊。我的黄 perf——
啊啊啊啊。（撒泼打滚）
所以求赞我的 CDEFG 题解。