題干：

Eva is trying to make her own color stripe out of a given one. She would like to keep only her favorite colors in her favorite order by cutting off those unwanted pieces and sewing the remaining parts together to form her favorite color stripe.

It is said that a normal human eye can distinguish about less than 200 different colors, so Eva's favorite colors are limited. However the original stripe could be very long, and Eva would like to have the remaining favorite stripe with the maximum length. So she needs your help to find her the best result.

Note that the solution might not be unique, but you only have to tell her the maximum length. For example, given a stripe of colors {2 2 4 1 5 5 6 3 1 1 5 6}. If Eva's favorite colors are given in her favorite order as {2 3 1 5 6}, then she has 4 possible best solutions {2 2 1 1 1 5 6}, {2 2 1 5 5 5 6}, {2 2 1 5 5 6 6}, and {2 2 3 1 1 5 6}.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive integer?N?(≤200) which is the total number of colors involved (and hence the colors are numbered from 1 to?N). Then the next line starts with a positive integer?M?(≤200) followed by?M?Eva's favorite color numbers given in her favorite order. Finally the third line starts with a positive integer?L?(≤10?4??) which is the length of the given stripe, followed by?L?colors on the stripe. All the numbers in a line a separated by a space.

Output Specification:

For each test case, simply print in a line the maximum length of Eva's favorite stripe.

Sample Input:

6 5 2 3 1 5 6 12 2 2 4 1 5 5 6 3 1 1 5 6

Sample Output:

7

題目大意：

Eva試著從給出的布條中選出她自己的彩色布條。她想要僅僅保留按照她最喜歡的順序排列的她喜歡的顏色，并且剪掉那些不喜歡的部分再將剩下的部分縫在一起來(lái)組成她最喜歡的彩色布條。所以她需要你的幫助來(lái)找出最好的結(jié)果。
注意結(jié)果可能不為1，但是你只需要告訴她最大的長(zhǎng)度。舉個(gè)例子，給你一個(gè) {2 2 4 1 5 5 6 3 1 1 5 6}.的彩色布條。如果Eva最喜歡的順序排列的最喜歡的顏色為{2 3 1 5 6},這樣她有4種可能的最佳方案 {2 2 1 1 1 5 6}, {2 2 1 5 5 5 6}, {2 2 1 5 5 6 6}, 和{2 2 3 1 1 5 6}。（注意? 最喜歡的順序排列? 的每個(gè)數(shù)字都不重復(fù)）

解題報(bào)告：

因?yàn)樽钕矚g的順序排列的每個(gè)數(shù)字都不重復(fù)，也就是說(shuō)我可以給這些數(shù)字重新定序。這樣就轉(zhuǎn)化為一個(gè)LIS問(wèn)題了。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<stack> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define FF first #define SS second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,int> PII; const int MAX = 2e5 + 5; int n,m,len; int a[222],b[MAX],dp[MAX],buf[MAX],top; int bk[222];//顏色出現(xiàn)的最后一個(gè)位置 int main() {memset(bk,-1,sizeof bk);//initcin>>n >> m;for(int i = 1; i<=m; i++) cin>>a[i],bk[a[i]] = i;cin>>len;for(int x,i = 1; i<=len; i++) {scanf("%d",&x);if(bk[x] != -1) {b[++top] = bk[x];}}for(int i = 1; i<=top; i++) {dp[i] = 1;for(int j = 1; j<i; j++) {if(b[i] >= b[j]) dp[i] = max(dp[i],dp[j]+1);}}printf("%d\n",*max_element(dp+1,dp+top+1));return 0 ; }

總結(jié)：

注意對(duì)于序列問(wèn)題，可以用數(shù)字大小來(lái)表示前后關(guān)系。

?

還有另一種方法：看不太懂

https://blog.csdn.net/tjj1998/article/details/79951718

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<string> #include<algorithm> #define INF 99999999 using namespace std; int N,M,L; int dp[210],v[210]; int main(){scanf("%d%d",&N,&M);int a;for(int i=0;i<M;i++){scanf("%d",&a);if(!v[a])v[a]=i+1;}scanf("%d",&L);for(int i=0;i<L;i++){scanf("%d",&a);if(v[a])for(int j=M;j>=v[a];j--){for(int k=v[a];k>=0;k--)dp[j]=max(dp[j],dp[k]+1);}}printf("%d\n",dp[M]);return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的【PAT - 甲级1045】Favorite Color Stripe(30分)（dp，LIS类问题）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。