DP 30题（上）

顺序对齐

考虑两个字符串右对齐的最佳解法。例如，有一个右对齐方案中字符串是 AADDEFGGHC 和 ADCDEGH。

AAD_DEFGGHC
 ADCDE__GH_

每一个数值匹配的位置值 2 分，一段连续的空格值 -1 分。所以总分是匹配点的 2 倍减去连续空格的段数，在上述给定的例子中，6 个位置(A, D, D, E, G, H)匹配，三段空格，所以得分 2×6+(-1)×3=9 ，注意，我们并不处罚左边的不匹配位置。若匹配的位置是两个不同的字符，则既不得分也不失分。
请你写个程序找出最佳右对齐方案。

输入

输入文件包含两行，每行一个字符串，最长50个字符。字符全部是大字字母。

输出

一行，为最佳对齐的得分。

样例

输入样例

AADDEFGGHC
ADCDEGH

输出样例

解法

然后从左边开始区间 DP，设 $f_{i,j}$ 为第一个字符串左边 $i$ 位，第二个字符串左边 $j$ 位的最大值。可以写出方程：

$f_{i,j}=\max \left\{\begin{aligned} &f_{i-1,j-1}+2 &(s1[i] = s2[j]) \\ &f_{i-1,j-1} &(s1[i] \neq s2[j]) \\ &f_{k,j}-1 &(1\le k < i) \\ &f_{i,k}-1 &(1\le k < j) \\ \end{aligned}\right.$

任务安排

个任务排成一个序列在一台机器上等待完成（顺序不得改变），这N个任务被分成若干批，每批包含相邻的若干任务。从时刻 0 开始，这些任务被分批加工，第 $i$ 个任务单独完成所需的时间是 $T_i$ 。在每批任务开始前，机器需要启动时间 $S$ ，而完成这批任务所需的时间是各个任务需要时间的总和（同一批任务将在同一时刻完成）。每个任务的费用是它的完成时刻乘以一个费用系数 $F_i$ 。请确定一个分组方案，使得总费用最小。
例如： $S=1$ ； $T={1,3,4,2,1}$ ； $F={3,2,3,3,4}$ 。如果分组方案是 ${1,2}, {3}, {4,5}$ ，则完成时间分别为 ${5,5,10,14,14}$ ，费用 $C={15,10,30,42,56}$ ，总费用就是 $153$ 。

输入

第一行是 $N(1\le N\le 5000)$ 。
第二行是 $S(0\le S\le 50)$ 。
下面 $N$ 行每行有一对数，分别为 $T_i$ 和 $F_i$ ，均为不大于 $100$ 的正整数，表示第 $i$ 个任务单独完成所需的时间是 $T_i$ 及其费用系数 $F_i$ 。

输出

一个数，最小的总费用。

输入样例

输出样例

解法

设 $f_i$ 为前 $i$ 个任务的最小价值。

$f_i=\min_{1\le j<i}\left\{f_{j-1}+\sum_{k=1}^i T_k \sum_{k=j}^i F_k \right\}+ S\sum_{k=i+1}^n F_k$

对于一个任务，我们枚举 $j$ ，使得任务 $j\sim i$ 为同一批次。总花费即包含

$f_{j-1}$ ，前 $j-1$ 个任务的花费；
$\sum_{k=1}^i T_k \sum_{k=j}^i F_k$ ， $j\sim i$ 任务的花费（不包含启动时间）
$S\sum_{k=i+1}^n F_k$ ，启动时间对后面任务花费的影响。

用前缀和预处理，复杂度 $O(n^2)$ 。

最大的算式

题目很简单，给出 $N$ 个数字，不改变它们的相对位置，在中间加入 $K$ 个乘号和 $N-K-1$ 个加号，（括号随便加）使最终结果尽量大。因为乘号和加号一共就是 $N-1$ 个了，所以恰好每两个相邻数字之间都有一个符号。例如：
N=5, K=2，5个数字分别为1、2、3、4、5，可以加成：
1×2×(3+4+5)=24
1×(2+3)×(4+5)=45
(1×2+3)×(4+5)=45
……

输入

输入文件共有二行，第一行为两个有空格隔开的整数，表示 $N$ 和 $K$ ，其中 $(2\le N\le 15, 0\le K\le N-1)$ 。第二行为 N个用空格隔开的数字（每个数字在0到9之间）。

输出

输出文件仅一行包含一个整数，表示要求的最大的结果

输入样例

5 2
1 2 3 4 5

输出样例

说明：
(1+2+3)×4×5=120

解法

经典区间 DP。设 $f_{i,j,k}$ 表示第 $i\sim j$ 个数用 $k$ 个乘号的最大值。

枚举区间分割点，左右两段可以加也可以乘，再枚举两段各用的乘号数即可。

$f_{i,j,k}=\max_{i\le k\le j}\left\{\begin{aligned} &f_{i,p,r_1} \times f_{p+1,j,p-r_1-1} &(r_1\le k-1)\\ &f_{i,p,r_2}+f_{p+1,j,p-r_2} &(r_2\le k)\\ \end{aligned}\right.$

BLAST

设有字符串 X，我们称在 X 的头尾及中间插入任意多个空格后构成的新字符串为 X 的扩展串，如字符串 X 为“abcbcd”，则字符串“abcb□cd”，“□a□bcbcd□”和“abcb□cd□”都是 X 的扩展串，这里 “□” 代表空格字符。
如果 A1 是字符串 A 的扩展串，B1 是字符串 B 的扩展串，A1 与 B1 具有相同的长度，那么我们定义字符串 A1 与 B1 的距离为相应位置上的字符的距离总和，而两个非空格字符的距离定义为它们的 ASCII 码的差的绝对值，而空格字符与其它任意字符之间的距离为已知的定值K，空格字符与空格字符的距离为 0。在字符串 A、B 的所有扩展串中，必定存在两个等长的扩展串 A1、B1，使得 A1 与 B1 之间的距离达到最小，我们将这一距离定义为字符串 A、B 的距离。
请你写一个程序，求出字符串A、B的距离。

输入

输入文件第一行为字符串 A，第二行为字符串 B，A、B 均由小写字母组成且长度均不超过 2000，第三行为一个整数 K，1≤K≤100，表示空格与其它字符的距离。

输出

输出文件仅一行包含一个整数，表示要求的字符串 A、B 的距离。

输入样例

cmc
snmn
2

输出样例

解法

设 $f_{i,j}$ 为第一个字符串前 $i$ 个字符，第二个字符串前 $j$ 个字符最小距离。

初始状态：

$f_{0,0}=0$ ， $f_{0,i}=f_{i,0}=i\times K$

每次转移要么不加空格，要么 A 加空格，要么 B 加空格。

$f_{i,j}=\min\left\{\begin{aligned} &f_{i-1,j-1}+|a_i-b_j|\\ &f_{i-1,j}+K\\ &f_{i,j-1}+K\\ \end{aligned}\right.$

书的复制

现在要把M本有顺序的书分给 $K$ 个人复制（抄写），每一个人的抄写速度都一样，一本书不允许给两个（或以上）的人抄写，分给每一个人的书，必须是连续的，比如不能把第一、第三、第四本数给同一个人抄写。现在请你设计一种方案，使得复制时间最短。复制时间为抄写页数最多的人用去的时间。

输入

第一行两个整数 $M$ ， $K$ ； $(K\le M\le 100)$
第二行 $M$ 个整数，第 $i$ 个整数表示第 $i$ 本书的页数。

输出

共 $K$ 行，每行两个正整数，第 $i$ 行表示第 $i$ 个人抄写的书的起始编号和终止编号。K行的起始编号应该从小到大排列，如果有多解，则尽可能让前面的人少抄写。

输入样例

9 3
1 2 3 4 5 6 7 8 9

输出样例

1 5
6 7
8 9

解法

显然可以设计状态 $f_{i,p}$ 代表前 $i$ 本书用 $p$ 个人抄的最小用时。

对于每个状态，考虑从之前的 $f_{j,p-1}$ 转移。此时状态即为之前的用时和这一个人抄书用时的最大值。

转移方程：

$f_{i,p}=\min_{p-1\le j<i} \left\{ \max \left\{ f_{j,p-1},\sum_{k=j}^i t_k \right\} \right\}$

为了输出答案，可以统计对于每个 $i$ ，是从哪一个 $j$ 转移过来的。最后根据 $f_{M,K}$ 的结果，即可得出答案。

最小乘车费用

某条街上每一公里就有一汽车站，乘车费用如下表：


公里数	1	2	3	4	5	6	7	8	9	10
费用	12	21	31	40	49	58	69	79	90	101

而一辆汽车从不行驶超过10公里。某人想行驶 $n$ 公里，假设他可以任意次换车，请你帮他找到一种乘车方案使费用最小（10 公里的费用比1 公里小的情况是允许的）。
编一程序，读入对乘车费用的描述，算出最小的价格

输入

输入文件共两行，第一行为10个不超过100的整数，依次表示行驶1～10公里的费用，相邻两数间用空格隔开；第二行为某人想要行驶的公里数。

输出

输出文件仅一行包含一个整数，表示该测试点的最小费用。

输入样例

12 21 31 40 49 58 69 79 90 101 
15

输出样例

解法

显然可以设 $f_i$ 表示行驶 $i$ 公里的最小费用。

$f_i = \min_{1\le j\le 10,i-j\ge 0}f_{i-j}+\text{cost}_j$

积木城堡

XC的儿子小XC最喜欢玩的游戏用积木垒漂亮的城堡。城堡是用一些立方体的积木垒成的，城堡的每一层是一块积木。小XC是一个比他爸爸XC还聪明的孩子，他发现垒城堡的时候，如果下面的积木比上面的积木大，那么城堡便不容易倒。所以他在垒城堡的时候总是遵循这样的规则。
小XC想把自己垒的城堡送给幼儿园里漂亮的女孩子们，这样可以增加他的好感度。为了公平起见，他决定把送给每个女孩子一样高的城堡，这样可以避免女孩子们为了获得更漂亮的城堡而引起争执。可是他发现自己在垒城堡的时候并没有预先考虑到这一点。所以他现在要改造城堡。由于他没有多余的积木了，他灵机一动，想出了一个巧妙的改造方案。他决定从每一个城堡中挪去一些积木，使得最终每座城堡都一样高。为了使他的城堡更雄伟，他觉得应该使最后的城堡都尽可能的高。
请你帮助小XC编一个程序，根据他垒的所有城堡的信息，决定应该移去哪些积木才能获得最佳的效果。

输入

第一行是一个整数N(N<=100)，表示一共有几座城堡。以下N行每行是一系列非负整数，用一个空格分隔，按从下往上的顺序依次给出一座城堡中所有积木的棱长。用-1结束。一座城堡中的积木不超过100块，每块积木的棱长不超过100。

输出

一个整数，表示最后城堡的最大可能的高度。如果找不到合适的方案，则输出0。

输入样例

2
2 1 –1
3 2 1 –1

输出样例

解法

考虑求每一座城堡所有可能的高度。然后用一个桶存每种高度出现的次数。最后在桶中找到出现次数为 $N$ 的最大高度即可。

设 $f_{i,j}$ 第 $i$ 座城堡，能否改成高度 $j$ 。和 01 背包转移相同，注意 $j$ 倒序遍历。

$f_{i,j} = \max{f_{i,j-w_k}} (1\le j \le \text{MAX\_HEIGHT},1\le k \le n)$

定义 $\text{cnt}_j 为 \sum f_{k,j}$ ，一遍求高度一遍维护 $\text{cnt}$ 即可。

筷子

A 先生有很多双筷子。确切的说应该是很多根，因为筷子的长度不一，很难判断出哪两根是一双的。这天，A先生家里来了 $K$ 个客人，A 先生留下他们吃晚饭。加上A 先生，A 夫人和他们的孩子小 A，共 $K+3$ 个人。每人需要用一双筷子。A先生只好清理了一下筷子，共N根，长度为 $T_1$ , $T_2$ , $T_3$ , $\dots$ , $T_N$ .现在他想用这些筷子组合成 $K+3$ 双，使每双的筷子长度差的平方和最小。(怎么不是和最小？？这要去问A先生了，呵呵)

输入

输入文件共有两行，第一行为两个用空格隔开的整数，表示 $N$ , $K$ $(1\le N\le 100, 0<K<50)$ ，第二行共有 $N$ 个用空格隔开的整数，为 $T_i$ . 每个整数为 $1～50$ 之间的数。

输出

输出文件仅一行。如果凑不齐 $K+3$ 双，输出 -1，否则输出长度差平方和的最小值。

输入样例

10 1
1 1 2 3 3 3 4 6 10 20

输出样例

说明:
第一双 1 1
第二双 2 3
第三双 3 3
第四双 4 6
$(1-1)^2+(2-3)^2+(3-3)^2+(4-6)^2=5$

解法

针对凑不齐的情况，直接特判是否 $N\ge 2(K+3)$ 即可，接下来考虑凑得齐的情况。

先把所有筷子排序。可证筷子两根一定不会出现交叉（因为出现交叉，不交叉一定差更小）。

则可有状态 $f_{i,j}$ 代表前 $i$ 根筷子组成了 $j$ 双的最小价值。

转移方程：

$f_{i,j} = \min_{2(j-1)\le k <i}\left\{f_{k,j-1}+\min_{k<p<i} (L_p-L_{p+1})^2\right\}$

针对 $\min_{k<p<i} (L_p-L_{p+1})^2$ 可以预处理。复杂度 $O(N^2K)$

护卫队

护卫车队在一条单行的街道前排成一队，前面河上是一座单行的桥。因为街道是一条单行道，所以任何车辆都不能超车。桥能承受一个给定的最大承载量。为了控制桥上的交通，桥两边各站一个指挥员。护卫车队被分成几个组，每组中的车辆都能同时通过该桥。当一组车队到达了桥的另一端，该端的指挥员就用电话通知另一端的指挥员，这样下一组车队才能开始通过该桥。每辆车的重量是已知的。任何一组车队的重量之和不能超过桥的最大承重量。被分在同一组的每一辆车都以其最快的速度通过该桥。一组车队通过该桥的时间是用该车队中速度最慢的车通过该桥所需的时间来表示的。问题要求计算出全部护卫车队通过该桥所需的最短时间值。

输入

输入文件第一行包含三个正整数(用空格隔开)，第一个整数表示该桥所能承受的最大载重量(用吨表示)；第二个整数表示该桥的长度(用千米表示)；第三个整数表示该护卫队中车辆的总数(n<1000)。接下来的几行中，每行包含两个正整数 W 和 S (用空格隔开)，W 表示该车的重量(用吨表示)，S 表示该车过桥能达到的最快速度(用千米/小时表示)。车子的重量和速度是按车子排队等候时的顺序给出的。

输出

输出文件应该是一个实数，四舍五入精确到小数点后1位，表示整个护卫车队通过该桥所需的最短时间(用分钟表示)。

输入样例

输出样例

75.0

解法

设 $f_i$ 表示前 $i$ 辆车过桥最短时间。

$f_i = \min_{0\le j <i \text{且} \sum_{k=j+1}^i{W_k}<\text{MAX\_LOAD}}\left\{f_j+ \dfrac{L}{\min_{j<k\le i}{S_k}}\right\}$

实际写程序只需将 $j$ 从 $i-1$ 往下遍历，维护当前车队重量。如果当前车队过重就跳出循环。

注意单位换算。

DOLLARS

在以后的若干天里戴维将学习美元与德国马克的汇率。编写程序帮助戴维何时应买或卖马克或美元，使他从100美元开始，最后能获得最高可能的价值。

输入

输入文件的第一行是一个自然数N，1≤N≤100，表示戴维学习汇率的天数。
接下来的N行中每行是一个自然数A，1≤A≤1000。第i+1行的A表示预先知道的第i+1天的平均汇率，在这一天中，戴维既能用100美元买A马克也能用A马克购买100美元。

输出

输出文件的第一行也是唯一的一行应输出要求的钱数(单位为美元，保留两位小数)。
注意：考虑到实数算术运算中进位的误差，结果在正确结果0.05美元范围内的被认为是正确的，戴维必须在最后一天结束之前将他的钱都换成美元。

输入样例

输出样例

266.66

样例解释 (无需输出)
Day 1 … changing 100.0000 美元= 400.0000 马克
Day 2 … changing 400.0000 马克= 133.3333 美元
Day 3 … changing 133.3333 美元= 666.6666 马克
Day 5 … changing 666.6666 马克= 266.6666 美元