题解 | #Favorite Color Stripe (30)#

将喜欢的颜色按顺序映射到递增的序列，就将问题转化为LIS

最终找出最大的dp[i]将其输出。

#include <bits/stdc++.h>

using namespace std;

const int maxc=210;
const int maxn=10010;
int hashtable[maxc];
int A[maxn],dp[maxn];
int main()
{
    int n,m,x;
    scanf("%d%d",&n,&m);
    memset(hashtable,-1,sizeof(hashtable));//将喜欢的颜色按顺序映射到递增的序列,不喜欢的均为-1
    for(int i=0;i<m;i++){
        scanf("%d",&x);
        hashtable[x]=i;
    }
    int L,num=0; //num存放喜欢的颜色序列长度（即原序列排除不喜欢颜色后得到的序列）
    scanf("%d",&L);
    for(int i=0;i<L;i++){
        scanf("%d",&x);
        if(hashtable[x]>=0){
            A[num++]=hashtable[x];
        }
    }
    int ans=-1; //记录最大
    for(int i=0;i<num;i++){ //按顺序算出dp[i]的值
        dp[i]=1; //边界初始条件
        for(int j=0;j<i;j++){
            if(A[j]<=A[i]&&dp[j]+1>dp[i]){
                dp[i]=dp[j]+1; //状态转移方程
            }
        }
        ans=max(ans,dp[i]);
    }
    printf("%d\n",ans);
    return 0;
}