题目内容

塔子最近在玩一款闯关游戏,其共有 $m$ 个回合，塔子有个技能：塔子起飞。总共可以使用 $x$ 次， 以下是对这个技能的简介:

1.每回合使用不超过一次。

思路

首先将题目转化为塔子完成整个关卡最少损失多少生命值，这时每个回合用不用塔子起飞所造成的贡献相对独立。

考虑第 $i$ 个回合用塔子起飞，会少损失 $v_i$ 点体力，并在之后的 $n-i$ 个关卡中每关增加 $1$ 点恢复，但是会少增加$cnt_i$点体力。 这里的 $cnt_i$ 代表之前用过的塔子起飞次数。

所以选择第$i$回合所带来的增益就是 $v_i+n-i-cnt_{i-1}$ 。由于每个位置的选择是独立的(也就是说你选第1个和你选第2个是没关系的。没规定你选了第1个必须选第2个。也没规定你选了第1个就不能选第2个)。所以我们就是要求:

$$\Large max\ \sum_{i \in \{i_1,i_2,...,i_x\}}^{} v_i+n-i-cnt_{i-1} \\ \Large = \sum_{i \in \{i_1,i_2,...,i_x\}}^{} v_i-i + \sum_{i \in \{i_1,i_2,...,i_x\}}^{} n -cnt_{i-1}$$