题目:http://pat.zju.edu.cn/contests/pat-a-practise/1045
题意:给定Eva喜爱的颜色序列,再给出一个颜色序列。要求在颜色序列中找到一个最长子串,子串中的颜色序列满足Eva喜爱的颜色序列中各个颜色的先后次序。输出该子串的最大长度。
思路:联想到最长递增子序列的情形。将Eva喜爱颜色序列中的每个颜色赋上权值,通过权值大小表示颜色先后次序。在待求解颜色序列中,做最长非递减子序列求解。不是Eva喜爱的颜色,直接忽略。O(N^2)DP求解。
代码:
#include<cstdio> #include<cstring> using namespace std; int favorite[201],color[10001],dp[10001]; int main() { int n,m,i,j,col,l; while(scanf("%d",&n)!=EOF) { for(i=1;i<=n;i++) favorite[i]=-1; scanf("%d",&m); for(i=0;i<m;i++) { scanf("%d",&col); favorite[col]=i; } scanf("%d",&l); for(i=0;i<l;i++) { scanf("%d",&color[i]); if(favorite[color[i]]==-1) { dp[i]=-1; continue; } dp[i]=1; for(j=0;j<i;j++) if(favorite[color[j]]!=-1&&favorite[color[j]]<=favorite[color[i]]) if(dp[j]+1>dp[i]) dp[i]=dp[j]+1; } int ans=0; for(i=0;i<l;i++) if(dp[i]>ans) ans=dp[i]; printf("%d\n",ans); } return 0; }