P2703 [NOI2006]千年虫 题解

· · 题解

我们注意到这个题本质是给定一个序列 a_i，然后需要给每个 a_i 加上一个非负整数得到序列 b_i，使得最后的序列满足这样的条件：

可以将整个序列分成奇数段，使得一段内的数都相等，且相邻两段之间满足 <,>,<,...> 的关系。即形成谷，峰，谷，峰...，谷这样的形式。

然后要最小化加上的数的和。

做法什么的可以看别的题解，这里主要证明一下结论。

结论是一定存在一组最优的 b_i 满足对于任意 i，\exists j,|i-j|\leq 2,b_i\in[a_j,a_j+1]（网上写的结论是 [a_j,a_j+2]，我是证的过程中发现结论实际上更强。）

我们首先考虑一下如果每段长度都是 1（即相邻两数都不相等），那么有显然的结论：若 i 在谷，那么 b_i=a_i，若 i 在峰，那么 b_i=\max(a_i,a_{i-1}+1,a_{i+1}+1)。因为一个谷的位置我们一定不会给它加，而峰的位置只要加到比相邻两数大即可。

然而现在麻烦的地方在于段长度不为 1 的时候。

我们的思路是先随便考虑一个合法的解，然后来改造它使得代价不增并使它满足一些特殊的性质。

对于一个 b_i=a_i 的位置，我们称它为固定点，对于一个 b_i\in [a_i,a_i+1] 的位置，我们称它为弱固定点。

下面讨论的段都是长度 >2 的段。

首先考虑段的两端，对于谷，若它某一端不是固定点，那么可以让这个数减一，段中与它相邻的数加一。对于峰，若它某一端里面一个数不是固定点，那么可以让这一端加一，里面那个数减一。

然后考虑段的内部。

对于谷，我们考虑找到内部相邻的三个位置，满足中间的位置不是弱固定点。那么我们可以让中间这个位置减二，其他两个位置加一。

对于峰，我们考虑找到内部相邻的三个位置，满足两边的位置都不是固定点。那么我们可以让中间这个位置加二，其他两个位置减一。

画画图就可以知道我们的这些操作都不改变解的合法性。不停地做这些操作，直到无法操作时，可以发现对于长度 >2 的段内部的数都满足上面提到的结论了。

然后我们把同一段看作一个数，它新的值 a'_i 是段内 a_i 的 \max。这时我们发现一段 [l,r] 的 a'_i 满足 a'_i=\max(a_l,a_{l+1})=\max(a_{r-1},a_r)

因为对于长度为 2 的段显然，而长度大于 3 的段经过上面的操作一定在与端点距离 \leq1 的位置存在固定点。

我们现在只关心长度为 2 的段..那么谷显然满足结论，因为 a_i=\max(a_i,a_{i+1}) 或 \max(a_{i-1},a_i)，而对于长度为 2 的段构成的峰，如果这个峰取到了自己的 a'，那么满足条件，否则仍然有一点棘手。

我们现在约定这个峰被它右边的谷限制。即右边的 a' 比较大。那么看起来当右边的谷长度为 2 时，峰中的左元素与谷中的固定点会相距 3..当然证到这里仍然得到了取值个数为常数，只不过稍微弱了一点。但是我们并不满足。

考虑如果峰中的右元素不是固定点，那么我们可以让峰中的右元素减一，谷中的左元素加一，此时峰的长度就减一，变成长度为 1 的峰。此时因为原来满足 b=a'+1，容易发现仍然满足条件。做不了这个操作的峰一定满足右元素是固定点，那么就满足性质了。 （这里注意一下每次我们操作完之后段的形态会变化，我们需要重新求 a' 然后得到新答案）

我们来总结一下：

长度为 1 谷：b_i=a_i

长度为 2 谷：\exists j,|i-j|\leq 1,b_i=a_j

长度 >2 谷：\exists j,|i-j|\leq 1,b_i=a_j 或 b_i\in[a_i,a_i+1]

长度为 1 峰：\exists j,|i-j|\leq 2,b_i\in [a_j,a_j+1]

长度为 2 峰：\exists j,|i-j|\leq 1,b_i=a_j

长度 >2 峰：\exists j,|i-j|\leq 1,b_i=a_j

综上，对于任意 i，\exists j,|i-j|\leq 2,b_i\in[a_j,a_j+1]。