P2703 [NOI2006] 千年虫

题目链接：P2703 [NOI2006] 千年虫 - 洛谷。

本题使用奇妙性质优化 DP。

题目描述

千年虫是远古时代的生物，时隔几千万年，千年虫早已从地球上销声匿迹，人们对其知之甚少。考古生物学家最近开始对其有了兴趣，因为一批珍贵的千年虫化石被发现，这些化石保留了千年虫近乎完整的形态。

理论科学家们根据这些化石归纳出了千年虫的一般形态特征模型，并且据此判定出千年虫就是蜈蚣的祖先！但科学家 J 发现了实际与理论的一些出入，他仔细的研究了上百个千年虫化石，发现其中大部分千年虫的形态都不完全符合理论模型，这到底是什么因素造成的呢？理论科学家 K 敏锐的指出，千年虫的形态保存在化石中很有可能发生各种变化，即便最细微的变化也能导致它不符合模型。

于是，摆在科学家面前的新问题诞生了：判断一个化石中的千年虫与理论模型的差距有多大？具体来说，就是根据一个千年虫化石的形态 $A$ ，找到一个符合理论模型的形态 $B$ ，使得 $B$ 是最有可能在形成化石时变成形态 $A$ 。理论学家提出的“千年虫形态特征模型”如下（如左图所示）：躯体由头、尾、躯干、足四大部分构成。

头，尾用一对平行线段表示。称平行于头、尾的方向为 $x$ 方向；垂直于 $x$ 的方向为 $y$ 方向；
在头尾之间有两条互不相交的折线段相连，他们与头、尾两条线段一起围成的区域称为躯干，两条折线段都满足以下条件：拐角均为钝角或者平角，且包含奇数条线段，从上往下数的奇数条垂直于 $x$ 方向。
每条折线段从上往下数的第偶数条线段的躯干的另一侧长出一条足，即一个上、下底平行于 $x$ 方向的梯形或矩形，且其中远离躯干一侧的边垂直于 $x$ 方向。

注意：足不能退化成三角形（即底边的长度均大于零），躯干两侧足的数目可以不一样。（如上图，左边有 $4$ 条足，右边有 $5$ 条足）

可见， $x$ - $y$ 直角坐标系内，躯干和所有足组成的实心区域的边界均平行或垂直于坐标轴。为了方便，我们假设所有这些边界的长度均为正整数。因此可以认为每个千年虫的躯体都由一些单位方格拼成。每个单位方格都由坐标 $(x, y)$ 唯一确定。设头尾之间的距离为 $n$ ，则我们可以用 $2 \times n$ 个整数来描述一条千年虫 $B$ （如右图）：将 $B$ 沿平行 $x$ 轴方向剖分成 $n$ 条宽度为 $1$ 的横条，每个横条最左边一格的 $x$ 坐标设为 $L_{i}$ ，最右一格的的 $x$ 坐标设为 $R_{i}$ 。则 $(n, L_{1}, L_{2}, \dots, L_{n}, R_{1}, R_{2}, \dots, R_{n})$ 就确定了一条千年虫。

由于岁月的侵蚀，在实际发现的化石中，千年虫的形状并不满足上面理论模型的规则，一些格子中的躯体已经被某些矿物质溶解腐蚀了。地质、物理、生物学家共同研究得出：

腐蚀是以格子为单位的，只能一整格被腐蚀；
腐蚀是分步进行的，每一步只有一格被腐蚀；
如果去掉一个格子后躯体不连通了，那么这个格子当前不会被腐蚀；
如果一个格子的左边邻格和右边邻格都还没被腐蚀，那么这个格子当前不会被腐蚀；
与头相邻的格子不能全部被腐蚀，与尾相邻的格子不能全部被腐蚀。

倘若满足上面五条，我们仍然可以用 $(n, L_{1}, L_{2}, \dots, L_{n}, R_{1}, R_{2}, \dots, R_{n})$ 来描述一个化石里头的千年虫的形态。其中 $L_{i} \leq R_{i}$ 。

例如下图：

现在你的任务是，输入一个化石里的千年虫的描述 $A$ ，找一个满足理论模型的千年虫的描述 $B$ ，使得 $B$ 可以通过腐蚀过程得以变为 $A$ ，且由 $B$ 转化为 $A$ 的代价（须被腐蚀的格子数）最少。输出此最小代价。

输入格式

第一行为一个整数 $n$ 。

以下 $n$ 行，每行两个整数，其中第 $i$ 行为两个整数 $L_{i}^{'}$ 、 $R_{i}^{'}$ ，用一个空格分开；保证输入数据合法。

输出格式

仅一行，为一个整数，表示最少代价。

输入输出样例 #1

输入 #1

输出 #1

说明/提示

【样例说明】

如图：

【评分方法】

本题没有部分分，你的程序的输出只有和我们的答案完全一致才能获得满分，否则不得分。

【数据范围】

对于 $30 %$ 的数据， $n \leq 100$ ， $R_{i} \leq 100$ ；

对于 $50 %$ 的数据， $n \leq 1000$ ， $R_{i} \leq 1000$ ；

对于 $70 %$ 的数据， $n \leq 10^{5}$ ， $R_{i} \leq 1000$ ；

对于 $100 %$ 的数据， $1 \leq n \leq 10^{6}$ ， $0 \leq L_{i} \leq R_{i} \leq 10^{6}$ 。

题解

问题转化

显然本题左右两侧的处理是相互独立的，我们以右侧处理为例。

转话题意如下。对于右侧的数列： $a = [4, 4, 5, 3, 2, 4, 3]$ ，添加若干个格子，使得整个数列出现“谷-峰-谷-……-谷-峰-谷”的模式。

  #    
###  # 
####0##
#######
#######

如上图所示，修改 $a_{5} = 3$ 可以使数列满足要求。

动态规划

用数列 $b$ 表示数列 $a$ 修正后的结果。

定义 $f (i, j, 0 / 1)$ 分别表示前 $i$ 个数中， $b_{i} = j$ 且 $b_{i}$ 为凹/凸的最小代价。容易得到状态转移方程

f (i, j, 0) = min {f (i - 1, j, 0), min_{k > j} {f (i - 1, k, 1)}} + j - a_{i}

该算法复杂度为 $O (n^{3})$ 。

决策优化

注意到状态转移的最优决策 $j$ 只会在 $[a_{p}, a_{p} + 2]$ 中产生，其中 $| p - i | \leq 2$ 。证明见：P2703 [NOI2006]千年虫题解 - 洛谷专栏。

使用该性质即可在有限的 $j$ 下完成转移，时间复杂度 $O (n)$ 。

注意本题二维数组可能超过内存限制，可使用滚动数组减少空间开销。