【每日一题】2021年3月17日题目预告

题号 NC24881
名称 Tower of Hay
来源 USACO
每日一题三期汇总贴~

如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情
欢迎给每日一题投稿，投稿需要提供牛客题库里的题目+题解 投稿有牛币奖励，可发站内信给王清楚或联系QQ 234186389
每日一题QQ群:659028468

题解

最开始大家可能会觉得，前i个草垛能组成的最大高度和最上层的最大宽度的有关系的，如果要dp，最大高度和最上层宽度至少要有一个出现在状态里，比如用 $f[i][j]$ 表示前 $i$ 个草垛堆成一堆最高的一层宽度为 $j$ 时的最大高度——复杂度不允许。
我们再仔细分析这个问题，刚刚的状态为什么离不开 $j$ ？
如果我们不知道最高层的宽度，上面再叠的时候就不一定能叠上去了无法转移，如果我分开用两个数组表示前 $i$ 个草垛能堆出的最大高度和最大高度下的宽度则错得更离谱——不一定前 $i$ 个堆得越高就越高，这样很有可能后面就宽度不够堆不上了。
但是，如果我们从后往前堆（即从最高层开始堆），问题会发生一些变化——后 $i$ 个如果堆了 $x$ 层，那么我们一定希望最下方那一层越小越好，而且，只要前 $i-1$ 个的宽度能比第 $x$ 层大，后 $i$ 个堆的 $x$ 层就一定能放上去，不会存在走入无解的死胡同这种情况。
所以我们倒着dp， $f[i]$ 表示后 $i$ 个草垛，其中第i个草垛是最后一层的最后一个时能达到的最大高度， $g[i]$ 存对应的最小宽度，考虑上一层的最后一个草垛是哪个 $f[i] = max(f[j] + 1)$
$g[i] = min(sum[i]- sum[j])$
其中 $j$ 从 $i+1$ 到 $n$ 枚举，且满足第 $i$ 到第 $j-1$ 个草垛宽度加起来大于 $g[j]$ ，即 $sum[i]- sum[j] \geq g[j]$
第 $i$ 到第 $j-1$ 个草垛宽度用后缀和维护求解（其实用前缀和也可以，搞清楚加一减一的关系就好）。
因为j要满足 $sum[i] - sum[j] \geq g[j]$ ，其实是在一个区间里面去找最小的j（j离i越近g越小)，这个区间的右界随着i的左移，是不往右移动的，所以用单调队列维护即可。
欢迎各位大佬来做题写题解，也欢迎大家踊跃在当日讨论贴中提问！