这类是dp入门题的经典类型,做一圈回忆一下.
目录:
题目不描述了,直接看数据就懂
输入数据
7
1 7 3 5 9 4 8
输出
4
分析:1 3 5 9 所以为 最长递增子序列的长度4
两个数组a[i]代表序列数值 dp[i]代表在i个序列值最长的递增子序列长度
a[i] = 1735948
dp[i] = 1 2 2 3 4 3 4
无论是什么数,初始值都会是1.因为至少我可以是个包含自己的序列,长度为1
当i=0,则dp[0]=1;当前只有这一个元素,所以长度为1
当i=1,则dp[1]=2;因为dp[i]会和之前每一个元素j代替进行比对,当a[i]<a[j],并且dp[j]+1>dp[i].则dp[i]=dp[j]+1
逻辑不难,用a算出dp就能明白了.
#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;
}
题目不描述了,直接看数据就懂
输入数据
2
abcdef
acdb
输出
3
别想难了,设定dp[i][j]为在,ij,位置上,的最长公共子序列.
两个for意味着两个队列的每一个都计算一遍,如果a[i]=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;
}
4: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
本文链接地址: 动态规划-各种子序列问题集合