PAT甲级1045
PAT甲级1045题目大意:给出总颜色数n(好像没什么用),eva喜欢的颜色数m,还有可供挑选的颜色数l,求出从l个颜色当中取出eva喜欢的颜色序列最大长度是多少(必须按她喜欢的顺序排列)LIS问题,这里尽量不要写find函数查找是不是eva喜欢的颜色,后面两个测试点会超时,用hash数组存放,如果不是eva喜欢的颜色就置为-1,若是则存放该颜色所在位置。然后开辟一个数组踢掉待选颜色中所有eva不
·
PAT甲级1045
题目大意:给出总颜色数n(好像没什么用),eva喜欢的颜色数m,还有可供挑选的颜色数l,求出从l个颜色当中取出eva喜欢的颜色序列最大长度是多少(必须按她喜欢的顺序排列)
LIS问题,这里尽量不要写find函数查找是不是eva喜欢的颜色,后面两个测试点会超时,用hash数组存放,如果不是eva喜欢的颜色就置为-1,若是则存放该颜色所在位置。然后开辟一个数组踢掉待选颜色中所有eva不喜欢的颜色即可。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n,m,l;
int favoriteColor[210];
int stripeColor[10010];
vector<int> a;
int favColor[210]; //记录是否是eva喜欢的颜色并且记录位置
int main(){
scanf("%d%d",&n,&m);
int length=0;
fill(favColor,favColor+210,-1);
for(int i=0;i<m;i++){
scanf("%d",&favoriteColor[i]);
favColor[favoriteColor[i]]=i;
}
scanf("%d",&l);
int dp[l];
for(int i=0;i<l;i++){
scanf("%d",&stripeColor[i]);
if(favColor[stripeColor[i]]!=-1) a.push_back(stripeColor[i]);
}
for(int i=0;i<a.size();i++){
dp[i]=1;
for(int j=0;j<i;j++){
if(favColor[a[j]]<=favColor[a[i]]&&dp[j]+1>dp[i])
dp[i]=dp[j]+1;
}
length=max(dp[i],length);
}
printf("%d",length);
system("pause");
return 0;
}
更多推荐
已为社区贡献1条内容
所有评论(0)