动态规划－各种子序列问题集合
这类是ｄｐ入门题的经典类型，做一圈回忆一下．
目录：
- １：最长递增子序列
- ２：最长公共子序列
- ３：回文串的问题
- ４：hdu4512（最长递增公共子序列问题）
１：最长递增子序列
题目不描述了，直接看数据就懂
输入数据
7
1 7 3 5 9 4 8
输出
４
分析：1 3 5 ９ 所以为 最长递增子序列的长度4分析：
两个数组ａ［ｉ］代表序列数值 ｄｐ［ｉ］代表在ｉ个序列值最长的递增子序列长度
ａ［ｉ］ ＝ １７３５９４８
ｄｐ［ｉ］ ＝ 1 2 2 3 4 3 ４
无论是什么数，初始值都会是１．因为至少我可以是个包含自己的序列，长度为１
当ｉ＝０，则ｄｐ［０］＝１；当前只有这一个元素，所以长度为１
当ｉ＝１，则ｄｐ［１］＝２；因为ｄｐ［ｉ］会和之前每一个元素ｊ代替进行比对，当ａ［ｉ］＜ａ［ｊ］，并且ｄｐ［ｊ］＋１＞ｄｐ［ｉ］．则ｄｐ［ｉ］＝ｄｐ［ｊ］＋１
逻辑不难，用ａ算出ｄｐ就能明白了．
模板代码：
#include <iostream>
#include "string.h"
using namespace std;
int d[1005];
int lis(int a[], int n)
{
int len = 1, i, j;
for(i = 0 ; i < n ; i++)
{//查询每一位置
d[i] = 1;
for(j = 0 ; j < i; j++)
//在当前位置之前的每一个位置
if(a[j] <= a[i] && d[j]+1 > d[i])
//把前面各个子序列中最后一个数不大于a【i】
d[i] = d[j] + 1;
//反复覆盖一个位置，
if(d[i] > len) len = d[i];
//每次留下最大的长度
}//继续循环
return len;
}
int main()
{
int a[1005],m,t,i;
while (cin>>m) {
memset(a,0,sizeof(a));
memset(d,0,sizeof(d));
for(i = 0 ; i <m ; i++)
cin>>a[i];
cout <<lis(a,m)<<endl;
}
return 0;
}２：最长公共子序列
题目不描述了，直接看数据就懂
输入数据
２
ａｂｃｄｅｆ
ａｃｄｂ
输出
３别想难了，设定ｄｐ［ｉ］［ｊ］为在，ij,位置上，的最长公共子序列．
两个ｆｏｒ意味着两个队列的每一个都计算一遍，如果ａ［ｉ］=b[i] 那么长度就是dp[i-1][j-1]+1．如果不等，那么应该继承上或者左边的原始计算值．
比如
a[] a b c
b[] a c
dp[i][j]：
j\i a b c
a 1 1 1
c 1 1 2
输出
2//最长公共子序列
#include <cstdio>
#include <cstring>
#define max(a,b) a>b?a:b
#define max1 1001
int dp[max1][max1];//保存当前位置最长公共子序列的个数
int main()
{
int n;
scanf("%d",&n);
while(n--)
{ char s1[max1],s2[max1];
int l1, l2, i, j;
memset(dp,0,sizeof(dp));
scanf("%s%s",s1,s2);
l1 = strlen(s1);
l2 = strlen(s2);
for(i = 1; i <= l1; i++)
for(j = 1; j <= l2; j++)
{
if(s1[i-1] == s2[j-1])
dp[i][j] = dp[i-1][j-1]+1;
else
dp[i][j] = max(dp[i][j-1],dp[i-1][j]);
}
printf("%d\n",dp[l1][l2]);
}
}３、回文串的问题
http://acm.nyist.net/JudgeOnline/problem.php?pid=37
题意：给你一串字符，问加最少的字符可以使它编程回文串…….
思路：就是求出它正反的最长公共子串，然后用len减去这个长度，就是最少要加的字符数……
这个很简单的．
#include<iostream>
#include<string>
#include<string.h>
using namespace std;
#define R 1003
#define C 1003
short len[R][C];
int main()
{
int n;
cin>>n;
while(n--)
{
memset(len,0,sizeof(len));
string a;
cin>>a;
string b=a;
int l=a.length();
for (int i=0;i<l;i++)
{
b[i]=a[l-i-1];
}
for (int i=0;i<a.length();i++)
for (int j=0;j<b.length();j++)
{
if(a[i]==b[j])
len[i+1][j+1]=len[i][j]+1;
else
len[i+1][j+1]= len[i][j+1]>len[i+1][j] ?len[i][j+1]:len[i+1][j] ;
}
cout<<l-len[a.length()][b.length()]<<endl;
}
return 0;
}４：hdu4512（最长递增公共子序列问题）
有一天，有n个人按顺序站在他的面前，他们的身高分别是h[1], h[2] … h[n]，吉哥希望从中挑出一些人，让这些人形成一个新的队形，新的队形若满足以下三点要求，则称之为完美队形： 1、挑出的人保持他们在原队形的相对顺序不变； 2、左右对称，假设有m个人形成新的队形，则第1个人和第m个人身高相同，第2个人和第m-1个人身高相同，依此类推，当然，如果m是奇数，中间那个人可以任意； 3、从左到中间那个人，身高需保证递增，如果用H表示新队形的高度，则H[1] < H[2] < H[3] …. < H[mid]。 现在吉哥想知道：最多能选出多少人组成完美队形？
思路：也是把字符串倒过来正反取最长递增公共子序列，但是需要注意的是，i<j，还有，在i~~j的过程中，也许会有一个很大的数，那么也是可以加进去的，
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
int dp[205][205],a[205];
int main()
{
int text;
scanf("%d",&text);
while(text--)
{
int n;
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
memset(dp,0,sizeof(dp));
int sum=0;
for(int i=1;i<=n;i++)
{
int maxx=0;
for(int j=n;j>i;j--)//直接倒过来
{
dp[i][j]=dp[i-1][j];//默认取值在判断之前就是上次计算的值
if(a[i-1]>a[j-1]&&dp[i][j]>maxx)
maxx=dp[i][j];
if(a[i-1]==a[j-1])
dp[i][j]=maxx+1;
if(dp[i][j]*2>sum)//正反一起算
sum=dp[i][j]*2;
for(int k=i+1;k<j;k++)
{
if(a[k-1]>a[j-1]&&dp[i][j]*2+1>sum)
sum=dp[i][j]*2+1;
}
}
}
printf("%d\n",sum);
}
return 0;
}原创文章，转载请注明： 转载自URl-team
本文链接地址: 动态规划－各种子序列问题集合