最大音量

动态规划

题意：给出一个初始值和一个变化序列 c，在第 i 步可以加上或减去 c[i]，求 n 步之后能达到的最大值。有一个限定值 maxlevel，在变化过程中值不能超过 maxlevel 也不能低于 0。

初步解法：搜索。每一步两种决策，及时阻止无效状态的搜索。

然后是（来自 lzw 大神的）剪枝：

1. 如果当前已经找到的答案达到了 Maxlevel 就直接退出；
2. 如果当前值加上后面所有的值也无法超过当前找到的答案就退出；
3. 对于重复状态只搜索一次。

从第三步看出来其实是个动规。

正解：

用 f(i, j) 表示第 i 步能否达到值 j，则

f(i, j) = f(i-1, j-c[i-1]) or f(i-1, j+c[i-1])

旅行

不知道什么类型

题意：一个矩形区域中分为空地和障碍，每行每列最多一个障碍且在对角线方向上障碍不会相邻。求所有任意两点的最短距离的平均值。行列数小于 1000。

初步解法：暴力。本来想对于每个点统计从其出发的长度为 x 的路径条数，后来发现无法解决重复计算的问题。

正解：

首先不考虑障碍。在没有障碍的情况下，任意两点之间的最短距离很明显就是曼哈顿距离，那么答案就是sum{ |xi-xj|+|yi-yj| }。但是枚举每个点的复杂度是四次方。

然后我们发现，对于任意两行 i 和 j，在两行中各选一个空地，则其 x 的差值必然等于 |i-j|。所以我们可以分开计算 x 的差值和 y 的差值。那么对于 i 和 j，x 的差值的和为 (第 i 行空地数*第 j 行空地数)*(|i-j|)*2。对于 y 的统计类似。

加入障碍后其实并没有太大的变化，只是对于某些点之间的最短路径长度不再等于曼哈顿距离，而是曼哈顿距离+2。

关于为什么是曼哈顿距离+2，其实要得益于题目中对障碍点的限制。这样可以保证任何点对之间相互到达不需要绕行多次，自己画图就能知道。

那么什么样的点对之间的最短距离需要 +2？贴上 NOI 导刊上的图：

这样的规律具体概括起来如下：

首先，考虑竖直方向上。对于一个障碍点，从它的下方到它的上方必然需要绕行。如果它的右边一列也有障碍点且在本障碍点的上方，那么从本障碍点的下方到右边这一列的障碍点上方显然也需要绕行，然后再往右找有没有连续的且高度不断递增的障碍点，要到达这些障碍点的上方都需要绕行。对于障碍点的左边做类似考虑。然后横向上也类似。

统计出有多少点对需要 +2后计入总答案即可。

舞蹈课

堆

题意：在一个队列中，每次找出相邻且舞蹈技术相差最小的异性，将其出列，出列后再次连成队列，不断重复此过程。人数少于 200000。

初步解法：模拟。0 分。

正解：

其实看到「每次选最小值」就应该用堆的。

我们把所有相邻的异性入堆，每次考虑栈顶元素。如果栈顶的两人有一人已经出列就直接将其弹出；否则将其从双向链表中删除，标记为已出列并计入答案，然后判断是否产生了新的异性舞伴，如果有就入堆。重复上述过程直到堆为空。

NOI导刊模拟题（1）