将Eva喜欢的颜色按顺序编个优先级，
2 3 1 5 6-> 1 2 3 4 5
然后读取stripe，将Eva不喜欢的先剔除掉，剩下的颜色替换为相应的优先级
2 2 4（去掉） 1 5 5 6 3 1 1 5 6 就变为：
1 1 3 4 4 5 2 3 3 4 5
接下来就是求最长上升子序列LIS的问题了，搞定~
O(n^2)的算法：
#include <iostream>
#include <cstdio>
#include <string.h>
#include <algorithm>using namespace std;
const int maxn=+;
int n,m;
int level[];
int vis[];
int a[maxn];
int main()
{
scanf("%d",&n);
scanf("%d",&m);
memset(vis,,sizeof(vis));
int tmp;
for(int i=;i<=m;i++){
scanf("%d",&tmp);
level[tmp]=i;
vis[tmp]=;
}
int cnt=;
int L;
scanf("%d",&L);
for(int i=;i<L;i++){
scanf("%d",&tmp);
if(vis[tmp]){
a[cnt++]=level[tmp];
}
}
//LIS最长上升子序列O(N^2)算法
int dp[maxn]; //dp[i]表示以a[i]结尾的最长上升子序列的长度
memset(dp,,sizeof(dp));
int ans=;
for(int i=;i<cnt;i++){
dp[i]=;
for(int j=;j<=i-;j++){
if(a[j]<=a[i] && dp[j]+>dp[i]){
dp[i]=dp[j]+;
}
}
if(dp[i]>ans)
ans=dp[i];
}
printf("%d\n",ans);
return ;
}
还想写一遍O(nlogn)的算法，但就是不知道为啥第三个样例一直WA，我觉得应该不是算法写错的问题。。。
先把代码贴出来吧，如果有人看到知道错在哪了，还请赐教~~谢谢
#include <iostream>
#include <cstdio>
#include <string.h>
#include <algorithm>using namespace std;
const int maxn=+;
int n,m;
int level[];
int vis[];
int a[maxn];/*找出满足条件d[j-1]< val <= d[j]的j,最后结果返回l即为j的值为什么第三个样例WA？？？？！！！！6
0
12 2 2 4 1 5 5 6 3 1 1 5 6*/
int Binary_Search(int l,int r,int val){
int mid;
while(l<=r){
mid=(l+r)>>;
if(val>a[mid])
l=mid+;
else
r=mid-;
}
return l;
}int main()
{
scanf("%d",&n);
scanf("%d",&m);
memset(vis,,sizeof(vis));
int tmp;
for(int i=;i<=m;i++){
scanf("%d",&tmp);
level[tmp]=i;
vis[tmp]=;
}
int cnt=;
int L;
scanf("%d",&L);
for(int i=;i<L;i++){
scanf("%d",&tmp);
if(vis[tmp]){
a[cnt++]=level[tmp];
}
}
//如果Eva喜欢的颜色在stripe里面没有的话，那么输出是0！然而第三个样例还是WA。。。
if(cnt==){
printf("0\n");
}
else{
//LIS最长上升子序列O(NlogN)算法
int dp[maxn]; //dp[i]表示长度为i的最长上升子序列中最小的末尾元素
dp[]=a[];
int len=;
for(int i=;i<cnt;i++){
if(dp[len]<=a[i]){
len++;
dp[len]=a[i];
}
else{
int idx=lower_bound(dp+,dp+len+,a[i])-dp;
dp[idx]=a[i];
}
}
printf("%d\n",len);
}
return ;
}
关于lower_bound函数，是在first和last中的前闭后开区间进行二分查找，返回大于或等于val的第一个元素位置。如果所有元素都小于val，则返回last的位置
(注意：此时的last在原数组是越界的)
