hdoj1423 最長上升公共子序列，hdoj1423最長上升

hdoj1423 最長上升公共子序列，hdoj1423最長上升

hdoj1423

題目分析： 
兩個數組a[n1] , b[n2], 求最長上升公共子序列。 
我們可用一維存儲 f[i] 表示 b 數組以 j 結尾， 與 a[] 數組構成的最長公共上升子序列。 對數組 d 的任意 j 位， 都枚舉 a[1 ~n1]。 
當a[i] == b[j] 時 ， 在1 ~ j - 1中 找出 b[k] 小於 a[ i ] 並且 d[k] 的值最大。 當 a[ i ] > b [j ] 時， 在0到j-1中，對於小於a[i]的，保存f值的最優解 （保存小於a [ i ] 並且 d[k]值最大的值所在的位置）。

#include<iostream>
#include<string>
#include<algorithm>
#include<string.h>
#include<cstring>
#include<cstdio>
using namespace std;

int t, n1, n2, a[505], b[505], d[505];

int LCIS()
{
    for(int i = 1; i <= n1; i++)
    {
        int k = 1;
        for(int j = 1; j <= n2; j++)
        {
            if(a[i] == b[j])
            {
                d[j] = max(d[j], d[k] + 1);
            }
            else if(a[i] > b[j])
            {
                if(d[k] < d[j])
                    k = j;
            }
        }
    }
    int mx = 0;
    for(int i = 1; i <= n2; i++)
        mx = max(mx, d[i]);
    return mx;
}
int main()
{
    cin >> t;
    while(t--)
    {
        memset(d, 0, sizeof(d));
        scanf("%d", &n1);
        for(int i = 1; i <= n1; i++)
            scanf("%d", &a[i]);
        scanf("%d", &n2);
        for(int i = 1; i <= n2; i++)
            scanf("%d", &b[i]);
        int ans = LCIS();
        printf("%d\n", ans);
        if(t != 0)
            printf("\n");
    }
    return 0;
}