P4922 [MtOI2018]崩坏3？非酋之战！ 题解

· · 题解

前言

刚入坑崩三，随便在主题库里搜了一下，发现竟然还有这样的题。。。

顺便说一句，现在新手第二天签到送空律。。。

Problem

题目大意：略。

数据范围：n \leq 10^4,Atk \leq 2^{64}-1。

Solution

分析一下，看到有八个技能，顿时感觉这个题不简单，后来一看： 闪避被大招完美压制；

  1. 爱酱的炸弹被技能完美压制；

  2. 犹大的誓约被大招完美压制；

  3. 奥托之光清除了燃烧状态，没用，因为显然攻击完后女武神就打不到 boss 了，只能靠燃烧，你清除了我还玩什么？

  4. 律者之力被技能和大招完美压制。

总结一下，大部分技能都没用，只有技能，大招，分支攻击有用。（其他技能的目的就是吓退你）

那么显然还是 DP 不了的，时间复杂度是 O(n^3)，还需要在简化。

使用邻项交换法，假设前面已经有 i 层燃烧， j 层时空减速：（忽略基础伤害，因为基础伤害相同，只有燃烧伤害不同）

相邻两个技能分别是技能和大招：

大招在前：Atk=i \times (j+1+5) \times atk /10+(i+1) \times (j+1) \times atk /10。

大招在后：Atk=(i+1) \times (j+1) \times atk/10+(i+1) \times (j+1+5) \times atk /10。

显然大招在后好一点。

若是分支攻击和大招：

大招在前：Atk=i \times (j+1+5) \times atk /10+i \times (j+1+1) \times atk/10。

大招在后：Atk=i \times (j+1+1) \times atk/10 +i \times (j+1+5+1) \times atk/10。

相同的结论。

其实我们可以这么想，技能和分支攻击对后面的攻击都是有加成的，相当于一个 buff,但是大招只是延长吃到 buff 的时间，所以把大招放在后面最优。

因此时间复杂度简化到了 O(n^2)，空间滚动树组即可。

至于 Atk \leq 2^{64}-1，按道理说要开 unsigned long long，不过这个题开 long long 也过去了。。。

Code

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+7232;
long long n;
long long hp,atk;
long long a,b,c,d;//技能，大招，分支
long long dp[2][N];
long long ans1,ans2=N;
long long mx(long long x,long long y){return x>y?x:y;}
long long mi(long long x,long long y){return x<y?x:y;}
int main()
{
    unsigned 
    cin>>n>>hp>>atk;
    a=8*atk/10;c=7*atk/10;d=atk/10;
    for(long long i=0;i<=n;i++)
    for(long long j=0;i+j<=n;j++)
    {
        long long k=n-i-j;
        b=12*atk/10+atk/10*i*(j+6);//一次大招的伤害计算
        if(i) dp[i&1][j]=mx(dp[i&1][j],dp[i-1&1][j]+a+d*(j+1)*(i-1));
        if(j) dp[i&1][j]=mx(dp[i&1][j],dp[i&1][j-1]+c+d*j*i);
        ans1=mx(ans1,dp[i&1][j]+k*b);
        if(dp[i&1][j]>=hp) ans2=mi(ans2,i+j);
        else if(dp[i&1][j]+k*b>=hp) ans2=mi(ans2,i+j+(hp-dp[i&1][j]+b-1)/b);
    }
    if(ans1<hp) printf("%lld\nMiHoYo Was Destroyed!",ans1);//翻译一下：mihoyo被摧毁？？？还是不要吧
    else printf("%lld\nTech Otakus Save The World!",ans2);
}

吐个槽：

要是真有不需要充能的女武神就好了。。。

为什么她们打一下要退一格？