1045. Favorite Color Stripe (30)

变相的非递减子序列问题：
常规动态规划解法，时间复杂度为O(n^2)：

#include<bits/stdc++.h>
using namespace std;
int main(){int n,m,l;scanf("%d%d",&n,&m);vector<int> fo(n+1,0);for(int i=1;i<=m;i++){int temp;scanf("%d",&temp);fo[temp]=i;}scanf("%d",&l);vector<int> st(l),dp(l,1);for(int i=0;i<l;i++) scanf("%d",&st[i]);for(int i=0;i<l;i++){for(int j=0;j<i;j++)if(fo[st[i]]!=0&&fo[st[j]]!=0&&fo[st[i]]>=fo[st[j]])dp[i]=max(dp[i],dp[j]+1);}int res=0;for(int i=0;i<l;i++){res=max(res,dp[i]);}printf("%d",res);
}

二分查找做法，时间复杂度为O(nlogn)，从柳神动态规划做法改进：
 

#include <bits/stdc++.h>
using namespace std;
int book[201], a[10001];
int main() {int n, m, x, l, num = 0;scanf("%d %d", &n, &m);for(int i = 1; i <= m; i++) {scanf("%d", &x);book[x] = i;}scanf("%d", &l);for(int i = 0; i < l; i++) {scanf("%d", &x);if(book[x] >= 1)a[num++] = book[x];}vector<int> lis;for(int i = 0; i < num; i++) {int temp = upper_bound(lis.begin(), lis.end(), a[i]) - lis.begin();if(temp < lis.size())lis[temp]=a[i];else lis.push_back(a[i]);}printf("%d", lis.size());return 0;
}