关键结论证明 P2046 【[NOI2010] 海拔】

Daniel13265 · 2022-02-21 15:23:55 · 题解

本文仅用于补充其他题解。其他题解未详细说明结论「存在至少一组最优方案使得每个交叉路口海拔都为 0 或 1，且海拔都为 0 和 1 的交叉路口分别仅构成一个极大四连通块」，本文予以简要证明。本文由讨论中单独提出，应@yurzhang 要求提交为题解（详见原讨论此题题解存在共同问题）。

下文「连通块」指「内部点高度相同的极大四连通块」。

对于一个方案，若存在高度小于 0 的点，则令所有这些点的高度为 0 更优，因为这些点之间的贡献减小为 0，而其他点的高度无论在调整前后都大于等于这些点的，所以这些点与其他点的贡献一定减小了。同理若存在高度大于 1 的点，则令所有这些点的高度为 1 更优。

现在每个点高度在 [0,1] 区间内，假设其不全为 0 或 1。对于所有不包含西北角的连通块，找到高度最小的一个（称为 S），这个连通块一定存在且不包含东南角。

• 若 S 不与西北角所在的连通块相邻，则将其高度调整为与其相邻的点中的最小高度一定更优，因为 S 内点之间的贡献不变为 0，而相邻点的高度无论在调整前后都大于等于这些点的，所以 S 内的点与其相邻点的贡献一定减小了。
• 若 S 与西北角所在的连通块相邻，则找到与之相邻的点中高度不为 0 且最小的（假设高度为 h），S 的高度一定在 0 与 h 之间。如果将 S 的高度看作自变量 x\in[0,h]，那么令 x=0 或 x=h 一定不更劣，因为 S 内点之间的贡献不变为 0，而 S 内的点与其相邻点的贡献是线性函数，最小值一定能在两端取到。

无论是哪种情况，都存在一种不更劣的、连通块更少的方案。不断进行调整，最终每个点的高度一定会停于 0 或 1。从而，一定存在一组最优方案使得点的高度都为 0 或 1。