1045 Favorite Color Stripe

LIS解法

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 10010;
const int maxc = 200;
int A[maxn];
int dp[maxn];
int HashTable[maxc];

int main()
{
    int n,m,x;
    scanf("%d%d",&n,&m);
    memset(HashTable,-1,sizeof(HashTable));

    for(int i=0;i<m;i++)
    {
        scanf("%d",&x);
        HashTable[x] = i;
    }

    int L,num=0;
    scanf("%d",&L);
    for(int i=0;i<L;i++)
    {
        scanf("%d",&x);
        if(HashTable[x]>=0)
        {
            A[num++] = HashTable[x];
        }
    }

    //使用LIS模板
    int ans = -1;
    for(int i=0;i<num;i++)
    {
        dp[i] = 1;
        for(int j=0;j<i;j++)
        {
            if(dp[j]+1>dp[i]&&A[i]>=A[j]) dp[i] = dp[j] + 1; 
        }
        ans = max(ans,dp[i]);
    }
    printf("%d\n",ans);
    return 0;
}

LCS解法

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxc = 210;
const int maxn = 10010;
int A[maxc],B[maxn],dp[maxc][maxn];

int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d",&A[i]);
    }

    int L;
    scanf("%d",&L);
    for(int i=1;i<=L;i++){
        scanf("%d",&B[i]);
    }

    //边界
    for(int i=0;i<=m;i++){
        dp[i][0] = 0;
    }
    for(int j=0;j<=L;j++){
        dp[0][j] = 0;
    }

    for(int i=1;i<=m;i++){
        for(int j=1;j<=L;j++){
            int MAX = max(dp[i-1][j],dp[i][j-1]);
            if(A[i]==B[j]){
                dp[i][j] = MAX + 1;
            }
            else{
                dp[i][j] = MAX;
            }
        }
    }
    printf("%d\n",dp[m][L]);
    return 0;
}