Topcoder SRM 563 Div1 500 SpellCards
程序员文章站
2023-02-18 18:34:27
题意 ~~[题目链接]~~这怎么发链接啊。。。。。 有$n$张符卡排成一个队列,每张符卡有两个属性,等级$li$和伤害$di$。 你可以做任意次操作,每次操作为以下二者之一: 把队首的符卡移动到队尾。 使用队首的符卡,对敌人造成$d_i$点伤害,并丢弃队首的$l_i$张符卡(包括你所使用的符卡)。如 ......
题意
[题目链接]这怎么发链接啊。。。。。
有\(n\)张符卡排成一个队列,每张符卡有两个属性,等级\(li\)和伤害\(di\)。
你可以做任意次操作,每次操作为以下二者之一:
把队首的符卡移动到队尾。
使用队首的符卡,对敌人造成\(d_i\)点伤害,并丢弃队首的\(l_i\)张符卡(包括你所使用的符卡)。如果队列不足\(l_i\)张符卡那么你不能使用。
求出造成的伤害的总和的最大值。
\(1<=n<=50, 1<=li<=50, 1<=di<=10000\)
sol
结论:如果选出的卡牌满足\(\sum l_i <= n\),那么总有一种方案打出这些牌
背包一下就van了
这个结论虽然看起来很显然 但是在考场上应该不是那么好发现吧
简单的证明一下:
序列上的问题比较难处理,我们把它们放到环上,这样可以消除操作1的影响
显然,选出的卡牌一定存在相邻的两个满足\(i - j > l_i\),也就是其中一个释放技能后不会干掉另一个(否则一定\(>n\))
我们把这张卡牌用掉,于是问题变成了一个相同的子问题。
#include<bits/stdc++.h> using namespace std; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int f[100]; class spellcards{ public: int maxdamage(vector<int> l, vector<int> d) { int n = l.size(); for(int i = 0; i < n; i++) for(int j = n; j >= l[i]; j--) f[j] = max(f[j], f[j - l[i]] + d[i]); return *max_element(f + 1, f + n + 1); } }; int main() { int n = read(); vector<int> l, d; for(int i = 1; i <= n; i++) l.push_back(read()); for(int i = 1; i <= n; i++) d.push_back(read()); cout << spellcards().maxdamage(l, d); } /* 7 1 2 2 3 1 4 2 113 253 523 941 250 534 454 */