PAT1045

PAT1045(LIS法)

#include <cstring>
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int color_num[201];
int stripe[10001];
int dp[10001];
int main()
{
    int N;
    cin >> N;
    int n;
    cin >> n;
    memset(color_num,-1,sizeof(color_num));
    int x;
    for(int i=0;i<n;i++)
    {
        cin >>x;
        color_num[x]=i;
    }
    int num=0;
    int L;
    cin >> L;
    for(int i=0;i<L;i++)
    {
        cin >> x;
        if(color_num[x]>=0)
            stripe[num++]=color_num[x];
    }
    int ans=0;
    for(int i=0;i<num;i++)
    {
        dp[i]=1;
        for(int j=0;j<i;j++)
        {
            if(stripe[i]>=stripe[j]&&dp[i]<dp[j]+1)
                dp[i]=dp[j]+1;
        }
        ans=max(dp[i],ans);
    }
    cout << ans;
    return 0;
}

总结：
散列加LIS
1.把喜欢的颜色顺序映射成递增数组
2.删除输入序列中不喜欢的颜色
3.用dp找LIS