题目链接：P2703 [NOI2006] 千年虫 - 洛谷。
本题使用奇妙性质优化 DP。
千年虫是远古时代的生物，时隔几千万年，千年虫早已从地球上销声匿迹，人们对其知之甚少。考古生物学家最近开始对其有了兴趣，因为一批珍贵的千年虫化石被发现，这些化石保留了千年虫近乎完整的形态。
理论科学家们根据这些化石归纳出了千年虫的一般形态特征模型，并且据此判定出千年虫就是蜈蚣的祖先！但科学家 J 发现了实际与理论的一些出入，他仔细的研究了上百个千年虫化石，发现其中大部分千年虫的形态都不完全符合理论模型，这到底是什么因素造成的呢？理论科学家 K 敏锐的指出，千年虫的形态保存在化石中很有可能发生各种变化，即便最细微的变化也能导致它不符合模型。
题目链接：P2470 [SCOI2007] 压缩 - 洛谷。
给一个由小写字母组成的字符串，我们可以用一种简单的方法来压缩其中的重复信息。压缩后的字符串除了小写字母外还可以（但不必）包含大写字母 R 与 M，其中 M 标记重复串的开始，R 重复从上一个 M（如果当前位置左边没有 M，则从串的开始算起）开始的解压结果（称为缓冲串）。
bcdcdcdcd 可以压缩为 bMcdRR，下面是解压缩的过程：
| 已经解压的部分 | 解压结果 | 缓冲串 |
|---|---|---|
| b | b | b |
| bM | b | . |
| bMc | bc | c |
| bMcd | bcd | cd |
| bMcdR | bcdcd | cdcd |
| bMcdRR | bcdcdcdcd | cdcdcdcd |
题目链接：P2145 [JSOI2007] 祖玛 - 洛谷。
这是一个流行在 Jsoi 的游戏，名称为祖玛。
精致细腻的背景，外加神秘的印加音乐衬托，彷佛置身在古老的国度里面，进行一个神秘的游戏——这就是著名的祖玛游戏。祖玛游戏的主角是一只石青蛙，石青蛙会吐出各种颜色的珠子，珠子造型美丽，并且有着神秘的色彩。
环绕着石青蛙的是载着珠子的轨道，各种颜色的珠子会沿着轨道往前滑动，石青蛙必需遏止珠子们滚进去轨道终点的洞里头，如何减少珠子呢？就得要靠石青蛙吐出的珠子与轨道上的珠子相结合，颜色相同者即可以消失得分！直到轨道上的珠子通通都被清干净为止。 或许你并不了解祖玛游戏。没关系。这里我们介绍一个简单版本的祖玛游戏规则。一条通道中有一些玻璃珠，每个珠子有各自的颜色，如图 1 所示。玩家可以做的是选择一种颜色的珠子（注意：颜色可以任选，这与真实游戏是不同的）射入某个位置。
$$ \def\TS{\mathrm{TS}} \def\Act{\mathrm{Act}} \def\AP{\mathrm{AP}} \def\Post{\mathrm{Post}} \def\O{\mathrm{O}} $$
摘要
题目 1-7 来自作业 1；
题目 8-12 来自作业 2；
13 及之后是考前划重点。
给定 $n$ 个矩阵，已知第 $i$ 个矩阵 $M_i$ 的大小为 $w_i$ 行 $w_{i+1}$ 列，而我们并不关心其内容。我们考虑将其按照顺序相乘（称其为链乘积）：
$$ M = M_1 \times M_2 \times \cdots \times M_n $$
矩阵乘法并不满足交换律，但是其满足结合律，因此我们可以通过合理安排结合顺序，尽可能减少需要的运算次数。在此题中，我们定义将一个大小为 $a \times b$ 的矩阵乘以一个大小为 $b \times c$ 的矩阵需要 $abc$ 次运算。
请你算出将题目所给的 $n$ 个矩阵进行链乘积所需的最少运算数。为了方便起见，你不需要构造方案。
题目链接：P1912 [NOI2009] 诗人小G - 洛谷。
本题是 DP 四边形不等式优化经典题型。
小 G 是一个出色的诗人，经常作诗自娱自乐。但是，他一直被一件事情所困扰，那就是诗的排版问题。
一首诗包含了若干个句子，对于一些连续的短句，可以将它们用空格隔开并放在一行中，注意一行中可以放的句子数目是没有限制的。小 G 给每首诗定义了一个行标准长度（行的长度为一行中符号的总个数），他希望排版后每行的长度都和行标准长度相差不远。显然排版时，不应改变原有的句子顺序，并且小 G 不允许把一个句子分在两行或者更多的行内。在满足上面两个条件的情况下，小 G 对于排版中的每行定义了一个不协调度, 为这行的实际长度与行标准长度差值绝对值的 $P$ 次方，而一个排版的不协调度为所有行不协调度的总和。
题目链接：P1081 [NOIP 2012 提高组] 开车旅行 - 洛谷。
小 $\text{A}$ 和小 $\text{B}$ 决定利用假期外出旅行，他们将想去的城市从 $1 $ 到 $n$ 编号，且编号较小的城市在编号较大的城市的西边，已知各个城市的海拔高度互不相同，记城市 $i$ 的海拔高度为$h_i$，城市 $i$ 和城市 $j$ 之间的距离 $d_{i,j}$ 恰好是这两个城市海拔高度之差的绝对值，即 $d_{i,j}=|h_i-h_j|$。
旅行过程中，小 $\text{A}$ 和小 $\text{B}$ 轮流开车，第一天小 $\text{A}$ 开车，之后每天轮换一次。他们计划选择一个城市 $s$ 作为起点，一直向东行驶，并且最多行驶 $x$ 公里就结束旅行。
小 $\text{A}$ 和小 $\text{B}$ 的驾驶风格不同，小 $\text{B}$ 总是沿着前进方向选择一个最近的城市作为目的地，而小 $\text{A}$ 总是沿着前进方向选择第二近的城市作为目的地（注意：本题中如果当前城市到两个城市的距离相同，则认为离海拔低的那个城市更近）。如果其中任何一人无法按照自己的原则选择目的城市，或者到达目的地会使行驶的总距离超出 $x$ 公里，他们就会结束旅行。
题目链接：P3571 [POI 2014] SUP-Supercomputer - 洛谷。
本题是经典斜率优化题型。
Byteasar has designed a supercomputer of novel architecture.
1 | |
本题是四边形不等式的应用。
高速公路旁边有一些村庄。高速公路表示为整数轴，每个村庄的位置用单个整数坐标 $X_i$ 标识。没有两个在同样地方的村庄。两个位置之间的距离是其整数坐标差的绝对值。
邮局将建在一些，但不一定是所有的村庄中。为了建立邮局，应选择他们建造的位置，使每个村庄与其最近的邮局之间的距离总和最小。
你要编写一个程序，已知村庄的位置和邮局的数量，计算每个村庄和最近的邮局之间所有距离的最小可能的总和。
题目链接：P5785 [SDOI2012] 任务安排 - 洛谷。
本题是经典 DP 斜率优化题型。
机器上有 $n$ 个需要处理的任务，它们构成了一个序列。这些任务被标号为 $1$ 到 $n$，因此序列的排列为 $1 , 2 , 3 \cdots n$。这 $n$ 个任务被分成若干批，每批包含相邻的若干任务。从时刻 $0$ 开始，这些任务被分批加工，第 $i$ 个任务单独完成所需的时间是 $T_i$。在每批任务开始前，机器需要启动时间 $s$，而完成这批任务所需的时间是各个任务需要时间的总和。
注意，同一批任务将在同一时刻完成。每个任务的费用是它的完成时刻乘以一个费用系数 $C_i$。