2133D-Chicken Jockey
简化题意从下到上有一排小鸡叠起来，他们的生命值依次为\(h_1,h_2,...,h_n\)，现在史蒂夫要将他们消灭，史蒂夫每次可以选择任意一只小鸡进行挥刀，使它生命值\(-1\),如果这只小鸡的生命值为\(0\)，它会消失，并且它上方的一叠小鸡会落在旁边（依然按照原先的顺序叠起来），此时最下方的小鸡会受到坠落高度的伤害，如果这只小鸡的生命值为\(0\)，它会消失，并且它上方的一叠小鸡...
直到所有小鸡消失。
思路
1.每只小鸡最多受到跌落伤害一次。当它跌落后，它会位于底层。看了官方的题解后，我想到可以自顶向下的考虑，先考虑史蒂夫是否要把次顶端的小鸡砍死，使最顶端的小鸡受到最大跌落伤害，同时保留了它下面的小鸡的位置不变，这样可以使他们的跌落伤害最大化，在考虑次顶，...
2.考虑\(dp\),\(dp_i\)表示史蒂夫砍死\(1~i\)只小鸡所需要最小的挥刀数，每只小鸡有两种方式，要么受到最大跌落伤害，要么前面全部死亡后受到\(1\)点伤害，$$dp_0 = 0, dp_1 = h_1, dp_i = min(dp_{i-1} + h_i - 1, dp_{i-2} + h_{i-1} + max(0, h_i - (i - 1))$$
code
#include using namespace std;long long t, n, dp, h;void solve(){ cin >> n; for(int i = 1;i > h; for(int i = 1;i
页:
[1]