DP 30题（下）

POWER

多瑞卡得到了一份有趣而高薪的工作。每天早晨他必须关掉他所在村庄的街灯。所有的街灯都被设置在一条直路的同一侧。
多瑞卡每晚到早晨5点钟都在晚会上，然后他开始关灯。开始时，他站在某一盏路灯的旁边。
每盏灯都有一个给定功率的电灯泡，因为多端卡有着自觉的节能意识，他希望在耗能总数最少的情况下将所有的灯关掉。
多端卡因为太累了，所以只能以 1m/s的速度行走。关灯不需要花费额外的时间，因为当他通过时就能将灯关掉。
编写程序，计算在给定路灯设置，灯泡功率以及多端卡的起始位置的情况下关掉所有的灯需耗费的最小能量。

输入

输入文件的第一行包含一个整数 $N$ ， $2≤N≤1000$ ，表示该村庄路灯的数量。
第二行包含一个整数 $V$ ， $1≤V≤N$ ，表示多瑞卡开始关灯的路灯号码。
接下来的 $N$ 行中，每行包含两个用空格隔开的整数 $D$ 和 $W$ ，用来描述每盏灯的参数，其中 $0≤D≤1000$ ， $0≤W≤1000$ 。 $D$ 表示该路灯与村庄开始处的距离(用米为单位来表示)， $W$ 表示灯泡的功率，即在每秒种该灯泡所消耗的能量数。路灯是按顺序给定的。

输出

输出文件的第一行即唯一的一行应包含一个整数，即消耗能量之和的最小值。注意结果不超过1,000,000,000。

输入样例

输出样例

解法

可以证明最后关的灯一定是端点上的灯。

设 $f_{i,j,0/1}$ 代表关掉区间 $[i,j]$ 的灯的耗电量， $0$ 代表最后关的是 $i$ ， $1$ 代表最后关的是 $j$ 。

$f_{i,j,0}=\min\left\{\begin{aligned}\ &f_{i+1,j,0}+(\sum_{k=1}^i W_k+\sum_{k=j+1}^n W_k)(D_{i+1}-D_i)\\ &f_{i+1,j,1}+(\sum_{k=1}^i W_k+\sum_{k=j+1}^n W_k)(D_{j}-D_i)\\ \end{aligned}\right.$

$f_{i,j,1}=\min\left\{\begin{aligned}\ &f_{i,j-1,0}+(\sum_{k=1}^{i-1} W_k+\sum_{k=j}^n W_k)(D_{j}-D_i)\\ &f_{i,j-1,1}+(\sum_{k=1}^{i-1} W_k+\sum_{k=j}^n W_k)(D_{j}-D_{j-1})\\ \end{aligned}\right.$

清扫

在要打扫国王的牧圈。已经30年没打扫了。所以这次的计划是用河水来冲。
牧圈排成整齐的格子，每相邻的两个之间都有门。要想让水进去，就必须打开这些门。这不是件容易的事情。因为有些圈里土堆得很高。因此打开门就很费劲。为了使花的力气最小，总是把门推向土低的一边。你的任务是计算最少得费多少劲。我们用土的厚度来描述这个值。

输入

第一行是宽度 $w$ 和高度 $h$ ，其中 $3 \le w,h \le 40$ 。以下 $h$ 行数据，描述了土的高度，也就是我们所浪费体力的度量。数据的范围在 $1$ 到 $100$ 之间。

输出

你得到的结果。所有的格子都必须进水。水是从左上角的格子进去的。

输入样例

输出样例

解法

题目描述写得很奇怪。重述题意：有 $w\times h$ 个点，开门花费两个格子的土厚度较小值。求花费最少的使所有格子连通的开门方案。

并不是 DP。对每个点建无向图，边权为两端点土的厚度较小值，然后最小生成树 Kruskal 即可。

零件分组

工厂生产一批棍状零件，每个零件都有一定的长度（ $L_i$ ）和重量（ $W_i$ ）。现在为了加工需要，要将它们分成若干组，使每一组的零件都能排成一个长度和重量都不下降的序列。请问至少要分成几组?

输入

第一行为一个整数 $N（N\le 1000）$ ，表示零件的个数。第二行有N对正整数，每对正整数表示这些零件的长度和重量，长度和重量均不超过 $10000$ 。

输出

仅一行，即最少分成的组数。

输入样例

5
8 4 3 8 2 3 9 7 3 5

输出样例

解法

等价于洛谷P1020 [NOIP1999 普及组] 导弹拦截。

求最长上升子序列即可（二维偏序）。

最小交换合并问题

在操场上沿一直线排列着 $n$ 堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的两堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。允许在第一次合并前对调一次相邻两堆石子的次序。
计算在上述条件下将n堆石子合并成一堆的最小得分和初次交换的位置。

输入

输入数据共有二行，其中，第 1 行是石子堆数 $n≤100$ ；第2行是顺序排列的各堆石子数（ $≤20$ ），每两个数之间用空格分隔。

输出

输出合并的最小得分。

输入样例

3
2 5 1

输出样例

解法

枚举第一次交换的可能，然后直接石子合并。
复杂度 $O(n^4)$ 。

潜水员

潜水员为了潜水要使用特殊的装备。他有一个带 2 种气体的气缸：一个为氧气，一个为氮气。让潜水员下潜的深度需要各种的数量的氧和氮。潜水员有一定数量的气缸。每个气缸都有重量和气体容量。潜水员为了完成他的工作需要特定数量的氧和氮。他完成工作所需气缸的总重的最低限度的是多少？
例如：潜水员有5个气缸。每行三个数字为：氧，氮的（升）量和气缸的重量：

如果潜水员需要 5 升的氧和 60 升的氮则总重最小为 249 （1，2 或者 4，5号气缸）。
你的任务就是计算潜水员为了完成他的工作需要的气缸的重量的最低值。

输入格式

第一行有 2 整数 $t$ ， $a$ （ $1\le t\le 21$ ， $1\le a\le 79$ ）。它们表示氧，氮各自需要的量。
第二行为整数 $n$ （ $1\le n\le 1000$ ）表示气缸的个数。
此后的n行，每行包括 $t_i$ ， $a_i$ ， $w_i$ （ $1\le t_i\le 21，1\le a_i\le 79，1\le w_i\le 800$ ）3 整数。这些各自是：第 $i$ 个气缸里的氧和氮的容量及汽缸重量。

输出

仅一行包含一个整数，为潜水员完成工作所需的气缸的重量总和的最低值。

输入样例

输出样例

解法

可以想到设 $f_{i,j}$ 表示氧气至少 $i$ 升，氮气至少 $j$ 升的最小重量。

对于气缸 $(O,N,W)$ 来说，有：

$f_{i,j} = \min\left\{f_{i,j},f_{p,q}+W\right\}$

其中 $i-O \le p \le i, j-N \le q \le j$ 。

复杂度 $O(\text{能过})$ 。

单词的划分

有一个很长的由小写字母组成字符串。为了便于对这个字符串进行分析，需要将它划分成若干个部分，每个部分称为一个单词。出于减少分析量的目的，我们希望划分出的单词数越少越好。你就是来完成这一划分工作的。

输入

第一行，一个字符串。（字符串的长度不超过 $100$ ）
第二行一个整数 $n$ ，表示单词的个数。（ $n\le 100$ ）
第 $3\sim n+2$ 行，每行列出一个单词。

输出

一个整数，表示字符串可以被划分成的最少的单词数。

输入样例

realityour
5
real
reality
it
your
our

输出样例

（原字符串可拆成real+it+your或reality+our，由于reality+our仅为两个部分，因此最优解为2，另外注意，单词列表中的每个单词都可以重复使用多次，也可以不用）

解法

显然设 $f_i$ 表示前 $i$ 个字符最少能拆成的单词数。

$f_i = \min_{(j+1)\sim i \text{是单词}}{f_j}+1$

火车票

从 Ekaterinburg 到 Sverdlovsk 的火车线路上有若干个站点。这条线路可以近似的表示为一条线段，火车站就是线段上的点。线路始于 Ekaterinburg，终于 Sverdlovsk。Ekaterinburg 被标号为 $1$ ，Sverdlovsk 被标号为 $n$ 。（ $n$ 为整条线路上的站点数）

线路上的任意两个站点间的直达票价是由它们间的距离决定的，票价根据以下规则制定：

$X$ 为两站的距离	价格
$0<X\le L_1$	$C_1$
$L_1<X\le L_2$	$C_2$
$L_2<X\le L_3$	$C_3$

如果两站的间距超过 $L_3$ ，则无直达车票。所以有时可能有必要买多张票，通过转车的方式，从一个站到达另一个站。
你的任务是，找出一种最经济的中转方案。

输入

第一行 $6$ 个整数 $L_1, L_2, L_3, C_1, C_2, C_3（1\le L_1<L_2<L_3\le 10^9, 1\le C_1<C_2<C_3\le 10^9）$ ，中间用空格分隔。
第二行一个整数 $n（2\le n\le 100）$ ，表示线路上的车站数。
第三行两个整数 $s$ 和 $t$ ，分别是起点和终点的编号。注意： $s$ 不一定小于 $t$ 。
以下的 $n-1$ 行，按据 Ekaterinburg 远近，每行描述了一个车站的位置。它包含一个整数，表示该车站据 Ekaterinburg 的距离。
任意两个车站的距离不超过 $10^9$ ，任意两个相邻的车站的距离不超过 $L_3$ 。

输出

一个整数，表示从给定的一个站到给定的另一个站的最小花费。

输入样例

3 6 8 20 30 40
7
2 6
3
7
8
13
15
23

输出样例

解法

设 $f_i$ 表示从 $s$ 出发，到达 $i$ 的最小花费。

$f_i = \min_{\operatorname{dist}(j,i)<L_3}{f_j+\operatorname{cost}(j,i)}$

$\operatorname{cost}(j,i)$ 可以 $O(1)$ 算出。

加油问题

个美国旅行代理上经常被要求去估计开车从一个城市旅行至另一个城市的最小费用。他有一个在通常路线上的大多数加油站的列表。列表包括了所有加油站的位置及当前每加仑汽油的价格。

为了简化估计费用的过程，代理商使用了以下的简化汽车驾驶员行为的规则：

除非汽车无法用油箱里的汽油达到下一个加油站（如果有的话）或目的地，在油箱里还有不少于最大容量一半的汽油时，驾驶员从不在加油站停下来。
在每一个停下的加油站，驾驶员总是将油加满。
在一个加油站停下之后，驾驶员将为旅程在快餐和糖果上花去2.00元。
在驶向加油站或目的地时，驾驶员不需要超过必须量的汽油。不需要“安全余量”。
驾驶员开始旅行时油箱总是满的
每个加油站付款时四舍五入到分（1元等于100分）。

你必须写一个程序以估计驾驶员在旅程上至少要为汽油和食品付多少钱。

输入

开始的2行给出了出发地和目的地的信息。数据项的后继行代表了路线上的加油站，每个加油站用一行表示。下面是输入数据中数据项的精确格式及其含义。
第一行：一个实数——从出发地到目的地的距离（英里）
第二行：三个实数及一个整数

第一个实数是汽车油箱的最大的容量（加仑）
第二个实数是汽车每加仑汽油可以行驶的英里数
第三个实数是汽车在出发地城市加满油箱的费用（单位：元）
整数（小于51）是路线上加油站的数目
接下来的每一行：两个实数
第一个实数是从出发地到加油站的距离（单位：英里）
第二个实数是该加油站出售的汽油每加仑的价格（单位：分）
数据项中的所有数据都是正的。一条路线上的加油站根据其到出发地的距离递增排列。路线上不存在这样的加油站，它到出发点的距离大于从出发点到目的地的距离。每条路线上的加油站都被适当的安排以使得任何汽车都能从出发地开到目的地。

输出

仅一行，一个实数（保留两位小数），表示最小的花费（单位：元）。

输入样例

475.6
11.9 27.4 14.98 6
102.0 99.9
220.0 132.9
256.3 147.9
275.0 102.9
277.6 112.9
381.8 100.9

输出样例

27.31

解法

和大模拟一样，细节较多（还好我只用口胡，就不用写代码了），但状态很好设计。

设 $f_i$ 为在第 $i$ 个加油站停下来的最少钱。

$f_i = \min{f_j+\operatorname{fuel}(j,i)}+2$

$\operatorname{fuel}(j,i)$ 为 $j$ 到 $i$ 的油钱（ $O(1)$ ）,要注意要满足从 $j$ 能开到 $i$ ，且油箱里的油少于一半。

答案统计所有能开到终点的 $f_i$ 最小值。

对话

前有两个人，一个名为"one"，另一个则叫"puton"。很奇怪，"one"除了称呼"puton"名字外，只对他说"out"和"output"两个单词；"puton"除了称呼"one"名字外，只对他说"in"和"input"两个单词。

最近人们在研究他们对话，但是，由于资料的混乱，其中可能有一些不是他们的对话。你的任务是鉴别一些句子，判断这些句子是否可能是他们的对话。（即，判断句子是否可以被划分成若干单词，这些单词只可以是"one"、“puton”、“out”、“output”、“in"和"input”）。

输入n个字符串，长度不超过200，表示一句句子。如果可能是那两个人的对话，则输出”YES”；否则，输出”NO”。

输入格式

第一行一个整数n，表示一共有n句句子。
此后每行一个字符串，表示一句句子。

输出格式

n行，每行一个”YES”或”NO”，表示你的判断结果。

输入样例

6
puton
inonputin
oneputonininputoutoutput
oneininputwooutoutput
outpu
utput

输出样例

YES
NO
YES
NO
NO
NO

解法

设 $f_i$ 代表前 $i$ 个字符是否是合法的。 $1$ 代表合法，反之不合法。

$f_i = \max_{(j+1)\sim i \text{是单词}} f_j$

观光游览

一条街道被分成 $m$ 格（ $1\le m\le 100$ ），还有 $n$ 个景点（ $1\le n\le 100$ ），分布在街道上。每个景点可以占据连续的若干格，并且有一个美学值 $v$ （ $0<v\le 100$ ）。现要组织 $k$ 个人考察这个街道（ $1\le k\le m$ ），每个人考察的区域是连续的若干格（不可为 $0$ 格），且任意两个人考察的区域不得相交，也不得有一个格子无人考察。对于任意一个人，如果它考察的区域中有一个风景点（风景点必须完整的位于这个区域），则它就得到了这个风景点的分值（美学值）。
你的任务是将街道的 $m$ 个格子分给 $k$ 个人去考察，使得总的分值最大。