题解 P4853 【yyf hates dagequ】

· · 题解

算法一（输出答案）

第一个点可以手算出答案为 1003000

时间复杂度：O(1)

期望得分：5 分

算法二（无技能）

直接模拟即可。

时间复杂度：O(n)

期望得分：10 分

算法三（有加分）

当连击数不为零且为 c_i 的倍数时，这个技能在这次击打中对答案的贡献为 p_i*s_i，所以扫一遍判断一下哪些技能的 c 能整除当前连击数，把贡献加起来就好了。

时间复杂度：O(\mathrm{score*n})

期望得分：25 分

算法四（蒟蒻ouuan第一次想到的dp）

用 f[i][j][k] 表示打 i 之前连击为 j ，“强判定效果”持续到 k ，打完 [i,n] 后的期望得分

转移的时候用二进制枚举子集来枚举一下每个技能是否触发，然后算出这种情况发生的概率，乘上这种情况的得分，加起来。

时间复杂度：O(\mathrm{n^3*2^{score+judge}*(score+judge)})

期望得分：15~25 分

算法五（数据分治）

使用数据分治结合算法三和算法四，可以获得更高的分数。

因为用算法四前 5 个点会爆空间，所以当 n>50 时就用算法三

时间复杂度：O(\mathrm{n>50?score*n:n^3*2^{score+judge}*(score+judge)})

期望得分：40~50 分

算法六（dew惨遭ouuan卡掉的dp）

用 f[i][j][k] 表示打 i 之前连击为 j ，“强判定效果”剩余持续时间为 k ，打完 [i,n] 后的期望得分

这样第三维的大小就从 O(n) 变成了 O(maxt)，时间复杂度也相应减少。

除此之外每次枚举子集之前可以先处理出哪些改判技能满足连击数为 c 的倍数，只用枚举这些技能就好了。而加分技能用算法三的方法来处理。

然而这样做会被第 15 和/或第 16 个点卡掉。

最坏情况时间复杂度：O(\mathrm{n^2*maxt*(judge*2^{judge}+score)})

期望得分：70~75 分

算法七（在dew的启发下ouuan最终想出的dp）

还是用 f[i][j][k] 表示打 i 之前连击为 j ，“强判定效果”剩余持续时间为 k ，打完 [i,n] 后的期望得分。

注意到每次枚举子集得到的结果只跟连击数有关，所以可以预处理出不同连击数的期望加分和改判不同次数的概率。

时间复杂度：O(\mathrm{n*score+n*judge*2^{judge}+n^2*maxt^2})

期望得分：80 分

算法八（wjyyyjulao的优化）

就在比赛前一天，wjyyy突然提出了一种优化...本来我是本着μ's只有9个人的原则不想增强数据的..后来想着不增强的话太水了估计有一堆AK..反正学园偶像又不只是μ's

（赛后补充：打脸，一个30+都没有）

（赛后后补充：还是有两位julao赛后20分钟内AC了Orz）

思路其实很简单，就是把改判技能按 t 降序排序，然后前面的改判发动了后面的改判就没用了，所以 \mathrm{judge*2^{judge}} 都被优化成了 \mathrm{judge}.

然后就可以愉快地过掉最后 20 分了。

而且算法四加了这个优化就稳 25 了，算法六加了这个优化就稳 80 了。

时间复杂度：O(\mathrm{n*score+n*judge+n^2*maxt^2})

期望得分：100 分

算法九

标程

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N=1005;
const int T=6;
const int S=1005;
const int J=1005;

struct Judge
{
    int c,p,t;
    bool operator<(Judge& b)
    {
        return t>b.t;
    }
} jud[J];

int n,a[N],sco[S][3],score,judge;
double f[N][N][T],scor[N],judg[N][T];

int main()
{
    int i,j,k,l,maxt=0;
    double pos;

    cin>>n>>score>>judge;

    for (i=0;i<score;++i)
    {
        cin>>sco[i][0]>>sco[i][1]>>sco[i][2];
    }
    for (i=0;i<judge;++i)
    {
        cin>>jud[i].c>>jud[i].p>>jud[i].t;
        maxt=max(maxt,jud[i].t);
    }

    sort(jud,jud+judge); //把改判技能按t排序

    for (i=0;i<n;++i) //枚举击打前连击为i次（也就是打完后连击是i+1次）
    {
        scor[i]=2.0*(i+2); //得分
        for (j=0;j<score;++j)
        {
            if ((i+1)%sco[j][0]==0)
            {
                scor[i]+=sco[j][1]*sco[j][2]/100.0; //期望加分
            }
        }

        pos=1.0;

        for (j=0;j<judge;++j) //按序枚举改判技能
        {
            if ((i+1)%jud[j].c==0)
            {
                judg[i][jud[j].t]+=jud[j].p/100.0*pos; //若发动则这次改判一定持续当前枚举的t
                pos*=1.0-jud[j].p/100.0; //不发动的概率
            }
        }
        judg[i][0]=pos; //一次都不发动
    }

    for (i=1;i<=n;++i)
    {
        cin>>a[i];
    }

    for (i=n;i>=1;--i)
    {
        for (j=0;j<i;++j)
        {
            for (k=0;k<=maxt;++k)
            {
                if (a[i]==0)
                {
                    f[i][j][k]=f[i+1][0][max(0,k-1)]; //若a[i]=0则下次连击必定为0，改判持续时间为max(0,k-1)
                }

                else if (a[i]==2||k>0)
                {
                    f[i][j][k]=scor[j]; //得分+期望加分

                    for (l=0;l<=maxt;++l)
                    {
                        f[i][j][k]+=f[i+1][j+1][max(l,k-1)]*judg[j][l]; //用改判不同次数进行转移
                    }
                }

                else
                {
                    f[i][j][k]=f[i+1][0][max(0,k-1)]+1.0; //与a[i]=0的不同在于还能得1分
                }
            }
        }
    }

    printf("%.6lf",f[1][0][0]);

    return 0;
}