SpellCards

作者：高杰

关键词：鸽巢原理 动态规划 背包

题目简述

有$n$张符卡排成一个队列，每张符卡有两个属性，等级$level_i$和伤害$damage _i$。

你可以做任意次操作，每次操作为以下二者之一：

• 把队首的符卡移动到队尾。

• 使用队首的符卡，对敌人造成$damage_i$点伤害，并丢弃队首的$level_i$张符卡（包括你所使用的符卡）。如果队列不足$level_i$张符卡那么你不能使用。

求出造成的伤害的总和的最大值。

数据范围

$1\le n\le 50, 1\le level\le 50, 1\le damage\le 10000$

算法一

首先由于第一种操作的存在，我们把它转化成一个环上的问题，并删去第一种操作。

接下来我们证明一个结论：

设$S$为一个符卡的集合，则存在一个方案能够使用$S$中所有符卡的充要条件为$\sum_{i\in S}level_i\le n$

必要性是显然的。由于使用一张符卡会使场上的符卡数减少$level$，因此使用的符卡的$level$之和不可能大于$n$，否则将存在一个时刻使场上的符卡数为负。

充分性是比较显然的。我们使用归纳法证明它：

首先，若$S$为空，则结论是显然的。

若$S$不为空，我们将$S$中的符卡在环上标记出来，按顺时针方向的顺序编号，把他们的$level$值记为$L_i$，到下一张$S$中的符卡的距离记为$D_i$。注意到有$\sum D_i=n$和$\sum L_i\le n$成立，根据鸽巢原理存在一个$i$使得$L_i\le D_i$，那么我们使用这张符卡不会丢弃任何$S$内的其它符卡，从而将$S$的规模缩小了$1$。

证明了这个结论，原题就变成了

求一个符卡的集合，满足$\sum level_i \le n$且$\sum damage_i$最大。

这是一个典型的01背包问题，可以用朴素的动态规划解决。