HDU 1423 Greatest Common Increasing Subsequence （最长公共上升子序列）【模板】_综合

浅谈一下最长公共上升子序列问题，LIS和LCS想必大家都会求，那么现在将他们组合起来，这时候应该怎么求呢？

我们不妨分析一下：

我们可以以LCS为基底，在其基础上加以改进，怎么改进呢？最长公共子序列，和我们现在要求的LCIS只差一个公共序列的顺序问题，那么我们可不可以把这个顺序问题加到代码中去呢？答案是可以的，用个maxn来维护B序列元素b[j]结尾的最长公共子序列的最大值，每次遍历B序列时更新其最大值，如果a[i]>当前的b[j]则更新maxn值，如果a[i]==b[j]，那么就更新以b[j]结尾的LCIS的值加1，这样一来，最后遍历完，dp[i]就表示以b[j]为结尾的LCIS的长度，我们只需要找出最大的dp[i]即可。

至于为什么只考虑b[j]序列，是因为LCIS中的元素b序列中有，那a序列中也一定有，所以只用考虑一个就好了。

【例题】

This is a problem from ZOJ 2432.To make it easyer,you just need output the length of the subsequence.

Input

Each sequence is described with M - its length (1 <= M <= 500) and M integer numbers Ai (-2^31 <= Ai < 2^31) - the sequence itself.

Output

output print L - the length of the greatest common increasing subsequence of both sequences.

Sample Input

15
1 4 2 5 -12
4
-12 1 2 4

Sample Output

【AC代码】

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=510;
int m,n;
int a[N],b[N];
int dp[N];int main()
{int t;scanf("%d",&t);while(t--){scanf("%d",&m);for(int i=1;i<=m;++i)scanf("%d",&a[i]);scanf("%d",&n);for(int i=1;i<=n;++i)scanf("%d",&b[i]);memset(dp,0,sizeof(dp));for(int i=1;i<=m;++i){int maxn=0;//维护最大值for(int j=1;j<=n;++j){if(a[i]>b[j]) maxn=max(maxn,dp[j]);//更新最大值if(a[i]==b[j]) dp[j]=maxn+1;}}int ans=0;for(int i=1;i<=n;++i)ans=max(ans,dp[i]); printf("%d\n",ans);if(t) cout<<endl;}return 0;
}