1423 greatest common increasing subsequence.cpp

威士忌的HDU题解.大概有260多题的源码。对于学习非常有好处。

/*
1423 Greatest Common Increasing Subsequence
Time Limit : 1000 ms  Memory Limit : 32768 K  Output Limit : 256 K

GUN C++
*/
//  时间复杂度 O(n^2), 空间复杂度 O(n^2)
/*
    l1为a的大小, l2为b的大小
    结果在ans中
    f记录路径，DP记录长度
    用a对b扫描，逐步最优化
*/

#include<string>
#include<iostream>
using namespace std;
const int MAXN=500;

int GCIS(int n, int a[], int m, int b[])
{
    int DP[MAXN+1];
    int i,j,k,max;

    memset(DP,0,sizeof(DP));
    for (i=1;i<=n;i++)
    {
        k=0;
        for (j=1;j<=m;j++)
        {
            if (b[j-1]<a[i-1] && DP[j]>DP[k])
                k=j;
            if (b[j-1]==a[i-1] && DP[k]+1>DP[j])
                DP[j]=DP[k]+1;
        }
    }
    for(max=0,i=1 ; i<=m ; i++)
        if( DP[i]>DP[max] )
            max=i;
        
    return DP[max];
}

int main()
{
    int i,j,k,t,n,m;
    int a[MAXN]={0},b[MAXN]={0};
    
    cin>>t;
    for(k=0;k<t;k++)
    {
        cin>>n;
        for(i=0;i<n;i++)
            cin>>a[i];
        cin>>m;
        for(i=0;i<m;i++)
            cin>>b[i];
            
        if(k!=0)
            cout<<endl;
        cout<<GCIS(n,a,m,b)<<endl;
    }
    return 0;
}