【PAT甲级】1045 Favorite Color Stripe (30 分)(DP)

 

题意:

输入一个正整数N(<=200),代表颜色总数,接下来输入一个正整数M(<=200),代表喜爱的颜色数量,接着输入M个正整数表示喜爱颜色的编号(同一颜色不会出现两次),接下来输入一个正整数L(<=10000),代表条带的长度,接着输入L个正整数表示条带上的颜色的编号。输出以喜爱颜色顺序排列的最长子串长度(不必每种颜色都有,只保证相对位置相同,同种颜色可连续)。

代码:

#define HAVE_STRUCT_TIMESPEC
#include<bits/stdc++.h>
using namespace std;
int a[10007],pos[207];
int dp[10007];
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n,m;
cin>>n>>m;
int color;
for(int i=1;i<=m;++i){
cin>>color;
pos[color]=i;//记录颜色的相对位置
}
int cnt=0;
int stripe;
int l;
cin>>l;
for(int i=1;i<=l;++i){
cin>>stripe;
if(pos[stripe])
a[++cnt]=pos[stripe],dp[cnt]=1;//记录条带上颜色在喜爱条带上的位置
}
int mx=0;
for(int i=1;i<=cnt;++i){
for(int j=1;j<i;++j)//以相对位置j结尾的都可以在后面加上以相对位置i结尾的颜色
if(a[j]<=a[i])
dp[i]=max(dp[i],dp[j]+1);//更新以相对位置i结尾的子串的长度
mx=max(mx,dp[i]);//选取最长长度作为答案
}
cout<<mx;
return 0;
}

上一篇:用工具软件远程链接数据库时报-1045 access denied错误


下一篇:mysql登录出现1045错误