[BZOJ4664]Count/[JOI Open 2016]摩天大楼

本文主要是介绍[BZOJ4664]Count/[JOI Open 2016]摩天大楼，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Count / 摩天大楼

题解

~~简单dp。~~

~~然而再想一遍又忘记怎么dp了，这种连续段dp确实很难想~~

首先发现这道题的贡献是绝对值，有点烦，考虑如何去掉绝对值。
我们可以对 $h$ 从大到小排序，这样加入 $h_{i}$ 时，已经加入的点会对其产生贡献的一定都比它大，所以我们可以直接加。
考虑每个点加入时会产生怎样的贡献：

如果加入的点单独成段且不靠墙，会令贡献加上 $2h_{i}$ 。
如果加入的点在某一段的两侧或靠一堵墙将不产生贡献。
如果加入的点两侧全是墙与段，它将起连接两段的作用，会令贡献减去 $2/1)h_{i}$ 。

于是我们很快就想到了一个dp方法，令 $dp_{i,j,t,k}$ 表示到第 $i$ 大的书，已经成了 $j$ 段，总贡献为 $t$ ，靠 $k$ 堵墙的方案数。
状态转移方程式也很好想。
但这样有个问题，因为贡献这一维带减法，所以它有可能有部分大于 $L$ 很多，这样空间复杂度就超了。
考虑对贡献的求法进行一下转化。