网站开发主要使用的技术,工商局网站年检怎么做,wordpress官方正式版,wordpress link正题
题目链接:https://www.luogu.com.cn/problem/P4922 题目大意
题目好长直接放了
在崩坏 3 中有一个叫做天命基地的地方#xff0c;女武神们将在基地中开派对与敌人们厮杀。
女武神们的攻击力为 atkatkatk#xff0c;她们将进行资源保卫战#xff01;
天命基地中有 …正题
题目链接:https://www.luogu.com.cn/problem/P4922 题目大意
题目好长直接放了
在崩坏 3 中有一个叫做天命基地的地方女武神们将在基地中开派对与敌人们厮杀。
女武神们的攻击力为 atkatkatk她们将进行资源保卫战
天命基地中有 111个 bossboss 的血量为 hphphpboss 不会攻击女武神。
现在有一条长度为 nnn 的道路道路的一头是 boss另外一头是女武神需要保卫的资源最开始 boss 每秒将会向资源移动 1 个单位长度。女武神们需要保护资源所以她们要攻击 boss。
我们将整条道路分成 nnn 个格子最开始资源在第 nnn 格女武神在第 111 格boss 在第 000 格。
因为女武神的手太短了所以只有当 boss 到达女武神当前那一格的时候女武神才会攻击 boss攻击完之后女武神会后退一格。
女武神有以下 888 种攻击方式每一格只能使用一种攻击方式
技能造成 80%atk80\% atk80%atk 的伤害并使 boss 获得 111 层燃烧 buff在之后的每秒钟额外受到 10%atk10\% atk10%atk 的伤害。(燃烧buff可以叠加)闪避造成 70%atk70\% atk70%atk 的伤害并使 boss 时间暂停 5s5s5s。5s5s5s 内 boss 无法移动且仍会受到燃烧伤害大招造成 120%atk120\% atk120%atk 的伤害使 boss 时间暂停 5s5s5s。分支攻击造成 70%atk70\% atk70%atk 的伤害并使 boss 时空减速使 boss 经过每一个格子的时间增加 1s1s1s。爱酱的炸弹使 boss 获得 111 层燃烧 buff并使 boss 愤怒移速 50%50\%50%。犹大的誓约造成 60%atk60\% atk60%atk 的伤害如果 boss 有燃烧 buff 则减少 1 层使 boss 时间暂停 4s4s4s。奥托之光造成 10%atk10\% atk10%atk 的伤害如果 boss 有燃烧 buff 则清除 buff使 boss 时间暂停 10s10s10s。律者之力造成 80%atk80\% atk80%atk 的伤害使 boss 的移动速度 100%100\%100%。
现在给你所有的信息让你帮助 disangan233 蒟蒻算一下他的女武神能否在 boss 触碰到资源前战胜 boss。
如果可以输出 boss 死亡时距离资源最远的格子编号。如果不可以请输出对 boss 造成的最大伤害。
对于 100%100\%100% 的数据保证 n≤10,000atk≡0(mod10)atk≤10,000maxAtk≤264−1n\leq 10,000 \qquad atk\equiv 0(\bmod\ 10)\qquad atk\leq 10,000\qquad \max Atk\leq 2^{64}-1 n≤10,000atk≡0(mod 10)atk≤10,000maxAtk≤264−1 解题思路
快三年之前的比赛上面写的题了那时候只会写O(n3)O(n^3)O(n3)的dpdpdp。什么一雪前耻
首先有很多技能一看就是没有用的有用的只有技能叠燃烧分支攻击叠减速大招。
然后大招一定是最后放的还有一个就是nnn的范围好像是可以O(n2)O(n^2)O(n2)卡一下的。
设fi,jf_{i,j}fi,j表示到前iii次jjj层燃烧然后剩下i−ji-ji−j层就是减速了。
这样dpdpdp就好了时间复杂度O(n2)O(n^2)O(n2)因为j≤ij\leq ij≤i所以常数是12\frac{1}{2}21 code
#includecstdio
#includecstring
#includealgorithm
#define ll unsigned long long
using namespace std;
const ll N11000;
ll n,hp,atk,maxs,mins,f[2][N];
signed main()
{scanf(%lld%lld%lld,n,hp,atk);atk/10ull;if(!atk)return printf(0\nMiHoYo Was Destroyed!);minsn;for(ll i0;in;i){for(ll j0;ji;j){ll ki-j1;//燃烧j层 减速k层 maxsmax(maxs,f[i1][j]atk*j*(n-i)*(5ullk)(n-i)*atk*12ull);minsmin(mins,i(hp-f[i1][j](j*5ullj*k12ull)*atk-1)/(j*5ullj*k12ull)/atk);f[~i1][j1]max(f[~i1][j1],k*j*atkatk*8ullf[i1][j]);//叠燃烧f[~i1][j]max(f[~i1][j],k*j*atkatk*7ullf[i1][j]);//叠减速 }}if(maxshp)printf(%lld\nTech Otakus Save The World!,mins);else printf(%lld\nMiHoYo Was Destroyed!,maxs);return 0;
}
