PTA1045 Favorite Color Stripe（最长不降子序列，dp）

分析：现对给出来的喜欢的序列做一个hash,比如他喜欢的序列2 3 1 5 6，映射成0，1，2，3，4。然后通过最长不降子序列来解决。
$dp[i]=max(dp[j]+1,1),其中满足0<=j<=i$

#include<iostream>
#include<algorithm>
#include<cstring>
#define inf 0x3f3f3f3f
using namespace std;
int n,len1,len2,maxx=-inf;
int ha[110000],a[110000],dp[110000];
int main(){
    std::ios::sync_with_stdio(false);memset(ha,-1,sizeof(ha));cin>>n;cin>>len1;for(int i=0;i<len1;i++){
    int x;cin>>x;ha[x]=i;}cin>>len2;for(int i=0;i<len2;i++){
    cin>>a[i];dp[i]=1;}//solvefor(int i=0;i<len2;i++){
    int ans1=ha[a[i]];if(ans1==-1) continue;for(int j=0;j<i;j++){
    int ans2=ha[a[j]];if(ans2==-1) continue;if(ans1>=ans2){
    dp[i]=dp[j]+1;}}maxx=max(dp[i],maxx);}cout<<maxx<<endl;return 0;
}