多序列dp
1265：【例9.9】最长公共子序列
【题目描述】
一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说，若给定序列X=<x1,x2,…,xm>�=<�1,�2,…,��>，则另一序列Z＝<z1，z2，…，zk>�＝<�1，�2，…，��>是X的子序列是指存在一个严格递增的下标序列<i1,i2,…,ik><�1,�2,…,��>,使得对于所有j=1,2,…,k有：
Xij=Zj���=��
例如，序列Z=<B,C,D,B>是序列X=<A,B,C,B,D,A,B>的子序列,相应的递增下标序列为<2,3,5,7>。给定两个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。例如，若X＝<A,B,C,B,D,A,B>和Y＝<B,D,C,A,B,A>，则序列<B,C,A>是X和Y的一个公共子序列,序列 <B,C,B,A>也是X和Y的一个公共子序列。而且，后者是X和Y的一个最长公共子序列．因为X和Y没有长度大于4的公共子序列。
给定两个序列X＝<x1，x2，…，xm>�＝<�1，�2，…，��>和Y=<y1,y2…．yn>�=<�1,�2…．��>．要求找出X和Y的一个最长公共子序列。
【输入】
共有两行。每行为一个由大写字母构成的长度不超过1000的字符串，表示序列X和Y。
【输出】
第一行为一个非负整数。表示所求得的最长公共子序列的长度。若不存在公共子序列．则输出文件仅有一行输出一个整数0。
【输入样例】
ABCBDAB BDCABA【输出样例】
4【提示】
最长公共子串（Longest Common Substirng）和最长公共子序列（Longest Common Subsequence，LCS）的区别为：子串是串的一个连续的部分，子序列则是从不改变序列的顺序，而从序列中去掉任意的元素而获得新的序列；也就是说，子串中字符的位置必须是连续的，子序列则可以不必连续。字符串长度小于等于1000。
思路：
状态 dp[i][j] s1的前i个字符和s2的前j个字符构成的最长公共子序列的长度
状态转移方程:
if(s1[i]==s2[j]) dp[i][j]=dp[i-1][j-1]+1;
else dp[i][j]=max(dp[i][j-1],dp[i-1][j])
#include<iostream>
using namespace std;
#include <limits.h>
const int N=1e3+10;
int dp[N][N];
int main()
{
string s1, s2; cin >> s1 >> s2;
int n = s1.size(), m = s2.size();//先计算不加空格的长度
s1 = ' '+s1; s2 = ' ' + s2;
//边界 dp[i][0]=dp[0][j]=0;//不需置
for (int i = 1; i <= n; i++)
{
for (int j =1; j <=m; j++)
{
if (s1[i] == s2[j])
dp[i][j] = dp[i - 1][j - 1] + 1;
else
dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
}
}
cout << dp[n][m];
return 0;
}
1276：【例9.20】编辑距离
【题目描述】
设A和B是两个字符串。我们要用最少的字符操作次数，将字符串A转换为字符串B。这里所说的字符操作共有三种：
1、删除一个字符；
2、插入一个字符；
3、将一个字符改为另一个字符。
对任意的两个字符串A和B，计算出将字符串A变换为字符串B所用的最少字符操作次数。
【输入】
第一行为字符串A；第二行为字符串B；字符串A和B的长度均小于2000。
【输出】
只有一个正整数，为最少字符操作次数。
【输入样例】
sfdqxbw gfdgw【输出样例】
4
思路：
多序列dp-编辑距离Edit-Distance
1.状态 dp[i][j] s1的前i个字符变为s2的前j个字符所需的最小操作数（即最短编辑距离）
2.状态转移方程
if(s1[i]==s2[j]) dp[i][j]=dp[i-1][j-1]
else dp[i][j]=min{dp[i-1][j]删除,dp[i][j-1]添加, dp[i - 1][j - 1]直接修改} + 1消耗一次操作数
#include<iostream>
using namespace std;
const int N = 2e3 + 10;
int dp[N][N];
int main() {
//边界 dp[i][0]=i dp[0][j]=j
string s1, s2;
cin >> s1 >> s2;
int n = s1.size(), m = s2.size();
s1 = ' ' + s1; s2 = ' ' + s2;//下标从1开始
//边界
for (int i = 1; i <= n; i++) dp[i][0] = i;
for (int j = 1; j <= m; j++) dp[0][j] = j;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (s1[i] == s2[j]) dp[i][j] = dp[i - 1][j - 1];
else dp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
}
}
cout << dp[n][m] << endl;
return 0;
}1286：怪盗基德的滑翔翼
【题目描述】
怪盗基德是一个充满传奇色彩的怪盗，专门以珠宝为目标的超级盗窃犯。而他最为突出的地方，就是他每次都能逃脱中村警部的重重围堵，而这也很大程度上是多亏了他随身携带的便于操作的滑翔翼。
有一天，怪盗基德像往常一样偷走了一颗珍贵的钻石，不料却被柯南小朋友识破了伪装，而他的滑翔翼的动力装置也被柯南踢出的足球破坏了。不得已，怪盗基德只能操作受损的滑翔翼逃脱。
假设城市中一共有N幢建筑排成一条线，每幢建筑的高度各不相同。初始时，怪盗基德可以在任何一幢建筑的顶端。他可以选择一个方向逃跑，但是不能中途改变方向（因为中森警部会在后面追击）。因为滑翔翼动力装置受损，他只能往下滑行（即：只能从较高的建筑滑翔到较低的建筑）。他希望尽可能多地经过不同建筑的顶部，这样可以减缓下降时的冲击力，减少受伤的可能性。请问，他最多可以经过多少幢不同建筑的顶部(包含初始时的建筑)？
【输入】
输入数据第一行是一个整数K(K<100)�(�<100)，代表有K�组测试数据。
每组测试数据包含两行：第一行是一个整数N(N<100)�(�<100)，代表有N�幢建筑。第二行包含N�个不同的整数，每一个对应一幢建筑的高度h(0<h<10000)ℎ(0<ℎ<10000)，按照建筑的排列顺序给出。
【输出】
对于每一组测试数据，输出一行，包含一个整数，代表怪盗基德最多可以经过的建筑数量。
【输入样例】
3 8 300 207 155 299 298 170 158 65 8 65 158 170 298 299 155 207 300 10 2 1 3 4 5 6 7 8 9 10【输出样例】
6 6 9
思路：
状态 dp[i] 以第i个元素为结尾的最长上升子序列
状态转移方程:if(a[j]<a[i])dp[i]=max(dp[i],dp[j]+1);最后求最长上升子序列和最长下降子序列的最大值
#include<iostream>
using namespace std;
#include <limits.h>
const int N=1e4+10;
int dp_u[N],dp_d[N],a[N];
int main()
{
int k; cin >> k;
while (k--)
{
int n; cin >> n;
memset(dp_u,0,sizeof dp_u);
memset(dp_d,0,sizeof dp_d);
memset(a,0,sizeof a);
for (int i = 1; i <= n; i++)
{
cin >> a[i];
//边界
dp_u[i]=dp_d[i]= 1;
}
for (int i = n; i >=1; i--)
{
for(int j=i+1;j<=n;j++)
if (a[j] < a[i])
dp_d[i] = max(dp_d[i], dp_d[j] + 1);
}
for (int i = 1; i <=n; i++)
{
for(int j=1;j<i;j++)
if (a[j] < a[i])
dp_u[i] = max(dp_u[i], dp_u[j] + 1);
}
int mx = 1;
for (int i = 1; i <= n; i++)
mx = max(max(mx,dp_d[i]),dp_u[i]);
cout << mx << endl;
}
return 0;
}
1297：公共子序列
【题目描述】
我们称序列Z=<z1,z2,...,zk>�=<�1,�2,...,��>是序列X=<x1,x2,...,xm>�=<�1,�2,...,��>的子序列当且仅当存在严格上升的序列<i1,i2,...,ik><�1,�2,...,��>，使得对j=1,2,...,k,有xij=zj���=��。比如Z=<a,b,f,c> 是X=<a,b,c,f,b,c>的子序列。
现在给出两个序列X和Y，你的任务是找到X和Y的最大公共子序列，也就是说要找到一个最长的序列Z，使得Z既是X的子序列也是Y的子序列。
【输入】
输入包括多组测试数据。每组数据包括一行，给出两个长度不超过200的字符串，表示两个序列。两个字符串之间由若干个空格隔开。
【输出】
对每组输入数据，输出一行，给出两个序列的最大公共子序列的长度。
【输入样例】
abcfbc abfcab programming contest abcd mnp【输出样例】
4 2 0
#include <limits.h>
#include<iostream>
using namespace std;
const int N=2e2+10;
int dp[N][N];
int main()
{
string s1, s2;
while (cin>>s1>>s2)
{
memset(dp,0,sizeof dp);
int n = s1.length(), m = s2.length();
s1 = ' ' + s1; s2 = ' ' + s2;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
if (s1[i] == s2[j])
dp[i][j] = dp[i - 1][j - 1] + 1;
else
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
cout << dp[n][m]<<endl;
}
return 0;
}
1298：计算字符串距离
【题目描述】
对于两个不同的字符串，我们有一套操作方法来把他们变得相同，具体方法为：
修改一个字符（如把“a”替换为“b”）;
删除一个字符（如把“traveling”变为“travelng”）。
比如对于“abcdefg”和“abcdef”两个字符串来说，我们认为可以通过增加/减少一个“g”的方式来达到目的。无论增加还是减少“g”，我们都仅仅需要一次操作。我们把这个操作所需要的次数定义为两个字符串的距离。
给定任意两个字符串，写出一个算法来计算出他们的距离。
【输入】
第一行有一个整数n。表示测试数据的组数。
接下来共n行，每行两个字符串，用空格隔开，表示要计算距离的两个字符串。
字符串长度不超过1000。
【输出】
针对每一组测试数据输出一个整数，值为两个字符串的距离。
【输入样例】
3 abcdefg abcdef ab ab mnklj jlknm【输出样例】
1 0 4
#include <limits.h>
#include<iostream>
using namespace std;
const int N=1e3+10;
int dp[N][N];
int main()
{
int k; cin >> k;
string s1, s2;
while (k--)
{
cin >> s1; cin >> s2;
memset(dp,0,sizeof dp);
int n = s1.length(), m = s2.length();
s1 = ' ' + s1; s2 = ' ' + s2;
for (int i = 1; i <= n; i++)
dp[i][0] = i;
for (int j = 1; j <= m; j++)
dp[0][j] = j;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
if (s1[i] == s2[j])
dp[i][j] = dp[i - 1][j - 1];
else
dp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]),dp[i-1][j-1])+1;
}
}
cout << dp[n][m]<<endl;
}
return 0;
}
