TopcoderSRM563Div1500SpellCards

题意

[题目链接]这怎么发链接啊。。。。。

有(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))

我们把这张卡牌用掉，于是问题变成了一个相同的子问题。

#includeusing 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 l, vector 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 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);}/*71 2 2 3 1 4 2113 253 523 941 250 534 454*/