hdu 1423 Greatest Common Increasing Subsequence(最长上升公共子序列)

http://acm.hdu.edu.cn/showproblem.php?pid=1423

好吧，对这道题表示无语。。。

给两个数字序列，求最长上升公共子序列的长度。所以可以先求最长公共子序列，用数组标记第一个序列每个i对应的到i为止最长公共子序列的长度，再求最长上升子序列。

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

int main()
{
    int test;
    int n,m;
    int a[510],b[510],c[510],d[510];
    int dp[510][510];
    scanf("%d",&test);
    for(int item = 1; item <= test; item++)
    {
        scanf("%d",&n);
        for(int i = 1; i <= n; i++)
            scanf("%d",&a[i]);
		scanf("%d",&m);
        for(int i = 1; i <= m; i++)
            scanf("%d",&b[i]);

        memset(dp,0,sizeof(dp));
        for(int i = 1; i <= n; i++)
        {
        	c[i] = -1;//c[i]对应到i为止最长公共子序列的长度
            for(int j = 1; j <= m; j++)
            {
				if(a[i] == b[j])
					dp[i][j] = dp[i-1][j-1]+1;
				else
					dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
				c[i] = max(c[i],dp[i][j]);
            }
        }

        int maxn = -1,pos = 1;
        for(int i = 1; i <= n; i++)
        {
        	d[i] = 1;//d[i]对应到i为止最长上升子序列的长度
        	for(int j = 1; j < i; j++)
			{
				if(a[j] < a[i] && d[i] < d[j]+1)
					d[i] = d[j]+1;
			}
			if(maxn < d[i])
			{
				maxn = d[i];
				pos = i;
			}
        }
        //输出最长上升子序列的下标对应的最长公共子序列的长度
        printf("%d\n",c[pos]);
        if(item < test) printf("\n");//注意换行，因此PE.
    }
    return 0;
}

hdu 1423 Greatest Common Increasing Subsequence(最长上升公共子序列),布布扣,bubuko.com

hdu 1423 Greatest Common Increasing Subsequence(最长上升公共子序列)

原文：http://blog.csdn.net/u013081425/article/details/20230151