P4954 题解

· · 个人记录

传送门

题意简述：按顺序给定 n 个干草堆，你要先选一个前缀放到第一层，再在剩下的里面选一个前缀放第二层 …… 以此类推，要求随着层数的增加，每一层干草堆的宽度之和不严格单调递减。 问：最多能堆多少层？

例如：9 8 2 1 5 5 可以分成 9|8|2 1 5|5，共四层。但是 1 2 100 就只能放一层。

看到这题一开始感觉像个贪心。感觉我们只要在堆的过程中，始终让最高层尽可能宽就行了。因为这样下一层的干草堆宽度之和也就能越大。

于是有一个思路：枚举前缀作为第一层，然后往后尽可能多取，直到下一层超过这一层，再递归地取再下一层。

很可惜有反例：100 3 2 1，按照贪心算法，会得出 100|3 2 1，但很显然应该是 100|3|2|1。

那反过来行不行呢？尝试把干草堆倒序，从高层开始堆，尽可能使最底层窄，这样可以更容易接上。

然鹅这也有反例：9 8 2 1 5 5 倒序得 5 5 1 2 8 9，贪心会划分成 5|5|1 2 8 9，但是正确答案是 5|5 1 2|8|9。

看得出来，前面的贪心使得后面的一层过宽，难以接上下一层。

于是我们大胆猜测：底层越小，可以堆的层数越高。

什么意思呢？若存在两种方案 opt1，opt2 且 opt1 的底层比 opt2 小，但是 opt2 的层数比 opt1 大：则一定能构造出方案 opt3 使得 opt3 的底层和 opt1 相同，层数与 opt2 相同。

于是我们就想到枚举第一层包含哪个前缀，尽可能使前缀小。如果当前前缀可以构造出一组方案，则用当前前缀构造出来的最大方案就是答案了。（注意我们此时已经把干草堆倒序）

但是这只是一个很空的说法。如何判断能不能构造成功？我们想到重复利用我们的结论：再尽量使前缀小，构造方案。

但是这么写就变成搜索了，复杂度肯定不能接受。于是我们推出一个 dp 的做法。