自动搬运

查看原文

来自洛谷，原作者为

	lenlen 一如既往，萬事勝意.

搬运于2025-08-24 22:05:18，当前版本为作者最后更新于2023-01-06 20:25:09，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前言

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

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

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);
}

吐个槽：

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

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