题目:http://pat.zju.edu.cn/contests/pat-a-practise/1045
题解:
DP。转换成求最长递增子序列。
代码:
#include<cstdio> #include<iostream> #include<cstring> #include<cmath> #include<string> #include<vector> #include<map> #include<set> #include<algorithm> #include<sstream> using namespace std; int dp[10005]; int num[205]; int stripe[10005]; int main() { int n,m,k,ans,x; memset(num,-1,sizeof(num)); scanf("%d",&n); scanf("%d",&m); for(int i=1; i<=m; ++i) { scanf("%d",&x); num[x]=i; } scanf("%d",&k); for(int i=1; i<=k; ++i) { scanf("%d",&x); stripe[i]=num[x]; } for(int i=1; i<=k; ++i) { if(stripe[i]>0) dp[i]=1; else dp[i]=0; } for(int i=2; i<=k; ++i) { if(stripe[i]==-1) dp[i]=0; else { for(int j=1; j<i; ++j) if(stripe[i]>=stripe[j]) dp[i]=max(dp[i],dp[j]+1); } } ans=0; for(int i=1; i<=k; ++i) if(dp[i]>ans) ans=dp[i]; printf("%d\n",ans); return 0; }