【HDU 1423】Greatest Common Increasing Subsequence【LCIS 裸题】

最朴素的算法

#include<bits/stdc++.h>
using namespace std;
int lenA,lenB,T;
int a[510],b[510];
int dp[510][510];
/*
	状态：
	a数组 考虑到i 
	b数组 考虑到j且以j结尾 
*/
int main(void)
{
	ios::sync_with_stdio(false);
	cin>>T;
	while(T--)
	{
		memset(dp,0,sizeof(dp));
		cin>>lenA;
		for(int i=1;i<=lenA;i++)cin>>a[i];
		cin>>lenB;
		for(int i=1;i<=lenB;i++)cin>>b[i];
		for(int i=1;i<=lenA;i++) 
		{
			for(int j=1;j<=lenB;j++)
			{
				dp[i][j] = dp[i-1][j];
				if(a[i]==b[j])
				{
					int Max = 0;
					for(int k=1;k<j;k++)if(b[j]>b[k])
					{
						Max = max(Max,dp[i-1][k]);
					}
					dp[i][j] = Max+1;
				}
				
				
			}
		}
		int ans = 0;
		for(int i=1;i<=lenB;i++)ans = max(ans,dp[lenA][i]);
		cout<<ans<<endl;
		if(T)cout<<endl;
	}
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
int lenA,lenB,T;
int a[510],b[510];
int dp[510][510];
/*
	状态：
	a数组 考虑到i 
	b数组 考虑到j且以j结尾 
*/
int main(void)
{
	ios::sync_with_stdio(false);
	cin>>T;
	while(T--)
	{
		cin>>lenA;
		for(int i=1;i<=lenA;i++)cin>>a[i];
		cin>>lenB;
		for(int i=1;i<=lenB;i++)cin>>b[i];
		for(int i=1;i<=lenA;i++) 
		{
			int Max = 0;
			for(int j=1;j<=lenB;j++)
			{
				dp[i][j] = dp[i-1][j];
				if(a[i]>b[j])Max = max(Max,dp[i-1][j]);
				if(a[i]==b[j])dp[i][j] = Max+1;				
			}
		}
		int ans = 0;
		for(int i=1;i<=lenB;i++)ans = max(ans,dp[lenA][i]);
		cout<<ans<<endl;
		if(T)cout<<endl;
	}
	return 0;
}

    #include <stdio.h>  
    #include <string.h>  
      
    #define MAX 501  
      
    int T;  
    int seq1[MAX], seq2[MAX];  
    int len1, len2;  
    int dp[MAX];  
      
    int LCIS(){  
        int i, j;  
        int Max;  
        memset(dp, 0, sizeof(dp));  
        for (i = 1; i <= len1; ++i){  
            Max = 0;  
            for (j = 1; j <= len2; ++j){  
                if (seq1[i] > seq2[j] && Max < dp[j])  
                    Max = dp[j];  
                if (seq1[i] == seq2[j])  
                    dp[j] = Max + 1;  
            }  
        }  
        Max = 0;  
        for (i = 1; i <= len2; ++i){  
            if (Max < dp[i])  
                Max = dp[i];  
        }  
        return Max;  
    }  
      
    int main(void){  
        int i;  
        scanf("%d", &T);  
        while (T-- != 0){  
            scanf("%d", &len1);  
            for (i = 1; i <= len1; ++i)  
                scanf("%d", &seq1[i]);  
            scanf("%d", &len2);  
            for (i = 1; i <= len2; ++i)  
                scanf("%d", &seq2[i]);  
            printf("%d\n", LCIS());  
            if (T)  
                putchar('\n');  
        }  
      
        return 0;  
    }