DP 30题（中）

胖男孩

麦克正如我们所知的已快乐地结婚，在上个月他胖了70磅。因为手指上的脂肪过多，使他连给他最亲密的朋友斯拉夫克写一个电子邮件都很困难。
每晚麦克都详细地描述那一天他所吃的所有东西，但有时当他只想按一次某键时往往会按了不止一次，并且他的胖手指还会碰到他不想要按的键，麦克也知道自己的手指有问题，因此他在打字的时候很小心，以确保每打一个想要的字符时误打的字符不超过3个，误打的字符可能在正确字符之前也可能在其之后。
当斯拉夫克多次收到读不懂的电子邮件后，他总是要求麦克将电子邮件发3遍，使他容易读懂一点。
编写程序，帮助斯拉夫克根据他所收到的三封电子邮件求出麦克可能写出的最长的信。

输入

输入文件包含了三行文本。每一行文本包括麦克信件的一种版本。其中所有的字符都由英文字母表中的小写字母组成并且不超过100个。

输出

输出文件中第一行即唯一的一行数据应该包含斯拉夫克根据所收到的电子邮件推测出的最长信件。你可以相信问题一定有解，但解不一定是唯一的。

输入样例

cecqbhvaiaedpibaluk
cabegviapcihlaaugck
adceevfdadaepcialaukd

输出样例

cevapiluk

解法

求三字符串最长公共子串即可。可以保证最长公共子串就是答案。

$f_{i,j,k}=\left\{\begin{aligned} &f_{i-1,j-1,k-1}+1, &a_i=b_i=c_j\\ &\max\left\{f_{i-1,j,k},f_{i,j-1,k},f_{i,j,k-1}\right\} , &\text{else}\\ \end{aligned}\right.$

对每个状态记录从哪里转移来的即可。

钓鱼

约翰是个垂钓谜，星期天他决定外出钓鱼 $h$ 小时 $(1\le h\le 16)$ ，约翰家附近共有 $n$ 个池塘 $(2\le n\le 25)$ ，这些池塘分布在一条直线上，约翰将这些池塘按离家的距离编上号，依次为 $L_1,L_2,\dots ,L_n$ ，约翰家门外就是第一个池塘，所以他到第一个池塘是不用花时间的，约翰可以任选若干个池塘垂钓，并且在每个池塘他都可以呆上任意长的时间，但呆的时间必须为5分钟的倍数，(5分钟为一个单位时间)，已知从池塘 $L_i$ 到池塘 $L_i+1$ 要化去约翰 $t_i$ 个单位时间，每个池塘的上鱼率预先也是已知的，池塘 $L_i$ 在第一个单位时间内能钓到的鱼为 $Fi (0\le F_i\le 100)$ ，并且每过一个单位时间在单位时间内能钓到的鱼将减少一个常数 $d_i(0\le di\le 100)$ ，现在请你编一个程序计算约翰最多能钓到多少鱼。

输入

输入文件第一行为一个整数 $n$ ，第二行为一个整数 $h$ ，第三行为 $n$ 个用空格隔开的整数，表示 $F_i(i=1,2,\dots ,n)$ ，第四行为n个用空格隔开的整数，表示 $d_i(i=1,2,\dots ,n)$ ，第五行为 $n-1$ 个用空格隔开的整数，表示 $t_i(i=1,2,\dots ,n-1)$

输出

输出一个整数，表示约翰最多能钓到的鱼的数量。

输入样例

输出样例

解法

显然可以令 $f_{i,j}$ 表示前 $i$ 个鱼塘用 $j$ 个单位时间最多可以钓到多少鱼。

$f_{i,j}=\max_{ \sum_{k=2}^{i-1}t_{k-1} \le p < j}{f_{i-1,p}+\operatorname{fish}(i,j-p-t_i)}$

定义 $\operatorname{fish}(i,t)$ 为在鱼塘 $i$ 钓 $t$ 分钟最多能钓上来的鱼。是一个等差数列，可以 $O(1)$ 求出。

文件排版

写电子邮件是有趣的，但不幸的是经常写不好看，主要是因为所有的行不一样长，你的上司想要发排版精美的电子邮件，你的任务是为他编写一个电子邮件排版程序。
完成这个任务最简单的办法是在太短的行中的单词之间插入空格，但这并不是最好的方法，考虑如下例子：

This is the example you  are
actually considering.

假设我们想将第二行变得和第一行一样长，靠简单地插入空格则我们将得到如下结果：

This is the example you  are
actually        considering.

但这太难看了，因为在第二行中有一个非常大的空白，如果将第一行的单词“are”移到下一行我们将得到较好的结果：

This  is  the  example   you
are  actually   considering.

当然，这必须对难看程度进行量化。因此我们必须给出单词之间的空格的难看程度，一个包含 $n$ 个空格符的空白段，其难看程度值为 $(n-1)^2$ ，程序的目的是使难看程度的总和最小化。例如，第一个例子的难看程度是 1+7×7=50，而第二个例子的难看程度仅为 1+1+1+4+1+4=12。
输出时，每一行的开头和结尾处都必须是一个单词，即每行开头和结尾处不能有空白。唯一例外的是该行仅有一个单词组成的情况，对于这种情况你可将单词放在该行开头处输出，此时如果该单词比该行应有的长度短则我们指定它的最坏程度为 500，当然在这种情况下，该行的实际长度即为该单词的长度。

输入

输入文件第一行是一个整数 $N$ ，表示该段要求达到的宽度， $1\le N\le 80$ 。该段文章由一个或多个单词组成，单词由 ASCII码值为 33 到 126（包含 33 和 126）的字符组成，单词与单词之间用空格隔开（可能超过一个）。单词长度不会超过段落要求达到的宽度。一段文字所有单词的总长度不会超过 10000 个字符，任何一行都不会超过 100 个字符，任何一个单词都在同一行内。

输出

对于每个段落，找出使其难看程度最小的排版形式并输出句子：“Minimal badness is B.”,B是指按可能的最好排版形式会发生的难看程度值。注意排版后文本行数任意，多余的空格也可删除。

输入样例

28
This is the example you  are
actually considering.

输出样例

Minimal badness is 12.

解法

首先，单词的内容，原来的换行都不重要。设原来共有 $m$ 个单词，长度分别为 $L_1,L_2,\dots,L_m$ 。

考虑 $f_{i,j}$ 代表前 $i$ 个单词占了 $j$ 行的最大值。接下来只需从前 $k$ 个单词占了 $j-1$ 行转移。

若每一行要多 $k$ 个空白，可以证明这 $k$ 个空白平均分配时平方和最小。

我们定义 $\operatorname{cost}(n,k)$ 代表一行有 $n$ 个词，还需包含 $k$ 个空格的代价。特别的若 $n=1$ ， $\operatorname{cost}(1,k)=500$ 。 $\operatorname{cost}(n,k)$ 可以在 $O(n)$ 时间内求出。

$f_{i,j}=\min f_{k,j-1}+\operatorname{cost}(i-k,N-(i-k-1)-\sum_{p=k+1}^i{L_p})$

在枚举 $k$ 时，倒序枚举，如果这一行已经放不下 $k+1\sim i$ 这些词了，就直接退出循环。

相似基因

大家都知道，基因可以看作一个碱基对序列。它包含了4种核苷酸，简记作A,C,G,T。生物学家正致力于寻找人类基因的功能，以利用于诊断疾病和发明药物。
在一个人类基因工作组的任务中，生物学家研究的是：两个基因的相似程度。因为这个研究对疾病的治疗有着非同寻常的作用。两个基因的相似度的计算方法如下：
对于两个已知基因，例如 AGTGATG 和 GTTAG，将它们的碱基互相对应。当然，中间可以加入一些空碱基-，例如：

A	G	T	G	A	T	-	G
-	G	T	-	-	T	A	G

这样,两个基因之间的相似度就可以用碱基之间相似度的总和来描述，碱基之间的相似度如下表所示：


	A	C	G	T	-
A	5	-1	-2	-1	-3
C	-1	5	-3	-2	-4
G	-2	-3	5	-2	-2
T	-1	-2	-2	5	-1
-	-3	-4	-2	-1	/

那么相似度就是：(-3)+5+5+(-2)+(-3)+5+(-3)+5=9。因为两个基因的对应方法不唯一，例如又有：

A	G	T	G	A	T	G
-	G	T	T	A	-	G

相似度为：(-3)+5+5+(-2)+5+(-1)+5=14。规定两个基因的相似度为所有对应方法中，相似度最大的那个。

输入

共两行。每行首先是一个整数，表示基因的长度；隔一个空格后是一个基因序列，序列中只含 A,C,G,T 四个字母。1<=序列的长度<=100。

输出

仅一行，即输入基因的相似度。

输入样例

7 AGTGATG
5 GTTAG

输出样例

解法

定义 $f_{i,j}$ 为第一个序列前 $i$ 个，第二个序列前 $j$ 个的相似度最大值。
定义 $\operatorname{sim}(x,y)$ 为两个基因的相似度，则有转移方程：

$f_{i,j}=\max\left\{\begin{aligned}\ &f_{i-1,j-1}+\operatorname{sim}(a_i,b_i)\\ &f_{i,j-1}+\operatorname{sim}(a_i,\texttt{'-'})\\ &f_{i-1,j}+\operatorname{sim}(\texttt{'-'},b_i)\\ \end{aligned}\right.$

饥饿的牛

牛在饲料槽前排好了队。饲料槽依次用 1 到 N(1<=N<=2000) 编号。每天晚上，一头幸运的牛根据约翰的规则，吃其中一些槽里的饲料。
约翰提供 B 个区间的清单。一个区间是一对整数 start-end,1<=start<=end<=N，表示一些连续的饲料槽，比如1-3,7-8,3-4等等。牛可以任意选择区间，但是牛选择的区间不能有重叠。
当然，牛希望自己能够吃得越多越好。给出一些区间，帮助这只牛找一些区间，使它能吃到最多的东西。
在上面的例子中，1-3 和 3-4 是重叠的；聪明的牛选择 {1-3，7-8}，这样可以吃到 5 个槽里的东西。

输入

第一行，整数 B (1<=B<=1000)
第 2 到 B+1 行，每行两个整数，表示一个区间，较小的端点在前面。

输出

仅一个整数，表示最多能吃到多少个槽里的食物。

输入样例

输出样例

解法

抽象问题：有 $n$ 个区间，选择任意个不相交区间，使得区间长度总和最长。

设 $f_i$ 表示 $i$ 位置是一个选择的区间尾，此时区间长度总和的最大值。

对于每个区间 $[l,r]$ ，有：

$f_r = \max_{0\le i\le l}f_i + (r-l+1)$

将区间按开头排序，再 DP 即可。

递增序列

给定一个数字串，请你插入若干个逗号，使得该数字串成为一个严格递增的数列且最后一个数要尽可能小，在这个问题中，前导的零是允许出现在数的前面的。

输入

输入数据仅含一行，为一个长度不超过80的数字串。

输出

输出一个严格递增且最后一数最小的数列，相邻两个数之间用一个逗号隔开，如果有多个数列满足要求，则输出第一个数最大的那个数列，若这样的解还不止一个，则输出第二个数最大的那个数列，以此类推。

输入样例

100000101

输出样例

100,000101

解法

令 $f_{i}$ 表示前 $i$ 个字符组成的严格递增数列的最后一个数的最小值。

$f_{i} = \min_{0\le j < i}{\operatorname{num}(j+1,i)} , \text{if}\operatorname{num}(j+1,i)>f_j$

在转移时，尽量转移 $f_j$ 最大的，并记录转移的 $j$ 。然后输出答案。

奇怪的电梯

呵呵，有一天我做了一个梦，梦见了一种很奇怪的电梯。大楼的每一层楼都可以停电梯，而且第 $i$ 层楼（ $1 \le i \le N$ ）上有一个数字 $K_i$ （ $0 \le K_i \le N$ ）。电梯只有四个按钮：开，关，上，下。上下的层数等于当前楼层上的那个数字。当然，如果不能满足要求，相应的按钮就会失灵。例如： $3, 3, 1, 2, 5$ 代表了 $K_i$ （ $K_1=3$ ， $K_2=3$ ，……），从 $1$ 楼开始。在 $1$ 楼，按“上”可以到 $4$ 楼，按“下”是不起作用的，因为没有 $-2$ 楼。那么，从 $A$ 楼到 $B$ 楼至少要按几次按钮呢？

输入

共二行。

第一行为三个用空格隔开的正整数，表示 $N, A, B$ （ $1 \le N \le 200$ ， $1 \le A, B \le N$ ）。

第二行为 $N$ 个用空格隔开的非负整数，表示 $K_i$ 。

输出

一行，即最少按键次数，若无法到达，则输出 -1。

输入样例

5 1 5
3 3 1 2 5

输出样例

解法

洛谷P1135 奇怪的电梯

洛谷原题。可以 BFS/DFS 搜索，即等价于 DP。

乘电梯

你拼命地工作到半夜，该回家了。你的办公室在摩天大楼的顶层。大楼有电梯系统。每部电梯工作的楼层是不一样的。每个电梯匀速运动，每上下一层的时间都是一个单位。现在你是大楼里唯一使用电梯的人。电梯随机地停在任意一个可能的位置。按下按钮，等一会儿电梯就会到了。显然电梯到的快慢取决于你在哪一层楼。你在某电梯服务范围的最高层会比在中间的时候等待更长的时间。更精确地，如果你的上面有a层楼，你的下面有b层楼，那么预计的等待时间将是：

$\text{E(waiting\ time)}=\left( \sum\limits_{i=1}^{a}{i}+\sum\limits_{i=1}^{b}{i} \right)\frac{1}{a+b+1}=\frac{a(a+1)+b(b+1)}{2(a+b+1)}$

你得写一个程序，计算下楼的最短时间。假设进出电梯和换电梯都不需要时间。

输入

第一行是电梯的数量和大楼层数。然后每行是一个电梯服务的最低层和最高层。
最多有200个电梯，大楼不超过10000层。
显然问题是有解的。不然你是怎么上去的呢？

输出

最短时间。精确到5位小数。

输入样例

输出样例

20.32308

解法

显然不需要坐电梯往上走。
设 $f_{i,j}$ 表示坐在第 $i$ 部电梯上，到达第 $j$ 层的最短时间。

$f_{i,j}=\min\left\{\begin{aligned}\ &f_{i,j+1}, &j\text{不是电梯顶层}\\ &f_{p,j}+\text{E(waiting\ time)}, &\text{电梯}p\text{停靠第}j\text{层}\\ \end{aligned}\right.$

LIGNJA

尼克每天上班之前都连接上英特网，接收他的上司发来的邮件，这些邮件包含了尼克主管的部门当天要完成的全部任务，每个任务由一个开始时刻与一个持续时间构成。
尼克的一个工作日为 $N$ 分钟，从第一分钟开始到第 $N$ 分钟结束。当尼克到达单位后他就开始干活。如果在同一时刻有多个任务需要完成，尼克可以任选其中的一个来做，而其余的则由他的同事完成，反之如果只有一个任务，则该任务必需由尼克去写成，假如某些任务开始时刻尼克正在工作，则这些任务也由尼克的同事完成。如果某任务于第 $P$ 分钟开始，持续时间为 $T$ 分钟，则该任务将在第 $P+T-1$ 分钟结束。
写一个程序计算尼克应该如何选取任务，才能获得最大的空暇时间。

输入

输入数据第一行包含两个用空格隔开的整数 $N$ 和 $K$ ， $1≤N≤10000$ ， $1≤K≤10000$ ， $N$ 表示尼克的工作时间，单位为分， $K$ 表示任务总数。

接下来共有 $K$ 行，每一行有两个用空格隔开的整数 $P$ 和 $T$ ，表示该任务从第 $P$ 分钟开始，持续时间为 $T$ 分钟，其中 $1≤P≤N$ ， $1≤P+T-1≤N$ 。

输出

输出文件仅一行包含一个整数表示尼克可能获得的最大空暇时间。

输入样例

输出样例

解法

设 $f_i$ 表示 $i$ 时刻做完了一个工作，此时的最大空暇时间。

对于每个工作 $[l,r]$ ，有：

$f_r = \max f_k + (l-k-1)$

其中 $k$ 要满足：

$f_k$ 有值；
$(k+1) \sim (l-1)$ 时间没有工作开始。

倒序遍历，如果不满足直接退出循环即可。

答案即为所有满足在 $i$ 时间后没有工作开始的 $f_i$ 加上 $N-i$ 的最大值。

POLYGON

对于一个多边形来说，在该多边形内任取两点，如果这两点连成的线段落在多边形内，则称这样的多边形为凸多边形。
平面上有N个坐标值为自然数的圆点。顶点数最多凸多边形是指由给定的圆点中的一部分组成的凸多边形，它包含最大可能的顶点数。原点，即坐标内中心 $(0，0)$ 必须是顶点数最多凸多边形的一个顶点。
编写程序求出这样的凸多边形的最大顶点数。注意一个多边形的连续的边不能是平行的。
入

输入

文件的第一行包含一个自然数 $N$ ， $2≤N≤100$ ，表示给定的圆点数。
下面的N行每行包含两个用空格隔开的自然数 $X$ 和 $Y$ ， $1≤X≤100$ ， $1≤Y≤100$ ，表示一个圆点的坐标值。所有的圆点是不相同的。

输出

输出文件的第一行也是唯一的一行应该包含顶点数最多凸多边形的顶点数。注意结果应不小于 $3$ 。

输入样例

输出样例

解法

设 $f_{i,j}$ 表示最后两个点为 $i$ 和 $j$ 情况下最大顶点数。

$f_{i,j}=\max{f_{k,i}+1} (k-i,i-j\text{可以构成凸多边形两条边})$

#include<bits/stdc++.h>
using namespace std;

const int N = 200;


struct Vec{
    int x,y;
};

Vec pts[N];
int cmp(const Vec &a,const Vec &b){
    // a.y/a.x > b.y/b.x;
    return a.y*b.x>b.y*a.x;
}


Vec cline(const Vec& a,const Vec& b){
    return {a.x-b.x,a.y-b.y};
}
int cp(const Vec &a,const Vec &b){
    return a.x*b.y - a.y*b.x;
}

int dp[N][N];


int main(){
    int n;
    scanf("%d",&n);
    pts[0].x=pts[0].y=0;
    pts[n+1].x=pts[n+1].y=0;

    for(int i=1;i<=n;i++){
        scanf("%d%d",&pts[i].x,&pts[i].y);
    }
    sort(pts+1,pts+n+1,cmp); 
    // 按斜率排序
    // 之后从上到下

    for(int i=1;i<=n;i++){
        dp[0][i]=1; // 这里=1（初始状态） 最后会补上原点
    }

    // 枚举最后一条边的两个点！ 
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n+1;j++){ // 有最后一个原点!!

            // 找可以的上一条边
            for(int k=0;k<i;k++){
                // 什么时候可以呢?
                // j 落在 ik 顺时针侧 叉乘负 
                // :顺负逆正

                if(cp(cline(pts[k],pts[i]),cline(pts[i],pts[j]))<0){
                    dp[i][j] = max(dp[i][j],dp[k][i]+1);
                }
            } 
        }
    }

    int ans = -1;
    for(int i=1;i<=n;i++){
        ans = max(ans,dp[i][n+1]);
    }
    printf("%d\n",ans);
    return 0;
}