PAT 1045 Favorite Color Stripe

这一题看题目就很容易想到动态规划。
题目大意是说给出一个序列，在给出的一个L长的序列中找到按照给出的序列的元素顺序排列的子序列的最长的长度。
如何找呢，
首先我们需要用哈希表来把给出的序列映射成 0-M-1，这样我们在新的L长的序列中再碰到给出的序列中的元素，可以确定它在给出序列中的相对位置是多少 （0到M-1中的其中一个），然后我们可以看在这个元素之前的元素能否和当前元素连接，求单独以这个元素的长度和与之前元素连接的长度的最大值。
最后，我们分别求以某一个元素为结尾所能构成的最长的子序列的长度。
完整代码如下

#include<bits/stdc++.h>#include<iostream>usingnamespacestd;vector<int>t;vector<int>sq;inth[205];intdp[205];intmain(){intN;cin>>N;intM;cin>>M;memset(h,-1,sizeof(h));for(inti=0;i<M;i++){intx;cin>>x;t.push_back(x);h[x]=i;}intL;cin>>L;for(inti=0;i<L;i++){intx;cin>>x;sq.push_back(x);}for(inti=0;i<L;i++){if(h[sq[i]]==-1){continue;}intx=h[sq[i]];//表示这个点在哈希表中的位置intpremaxx=0;for(intj=0;j<=x;j++){premaxx=max(premaxx,dp[j]);}dp[x]=max(premaxx+1,dp[x]);}intans=0;for(inti=0;i<M;i++){ans=max(ans,dp[i]);}cout<<ans<<endl;return0;}

注意：与当前元素前面的元素作连接时包括当前元素的本身

for(intj=0;j<=x;j++){premaxx=max(premaxx,dp[j]);}

时间复杂度O（n^2)