點擊鏈接PAT甲級-AC全解匯總

題目：
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

題意：
按照給定順序，從一串數種找出與該順序相符合的子序列最大長度。

沒有學過算法，這種題剛上來有點蒙，看了各路大神的dp思路，還是覺得柳神寫得最清楚。借鑒了一下思路。學海無涯。

思路：
先把數串過濾不在排名中的數字，剩下的最次長度也是1；
從前往后對于對于每個數而言，到此為止的最大長度（是以該節點為終點，不然沒法考慮到排名為51111的情況），分兩種情況

• 如果前面沒有比自己排名低的，那么以此為end最大長度就是1；
• 如果前面有比自己排名低的，那么以此為end最大長度就是之前最大比自己排名低的那個數作為end的長度+1

我的代碼：

#include<bits/stdc++.h> using namespace std;int main(){int N,M,L;cin>>N>>M;int rank[N+1]={0};for(int i=1;i<=M;i++){int num;cin>>num;rank[num]=i;//rank[2]=1 數字2的排名是1}cin>>L;vector<int>nums;for(int i=0;i<L;i++){int num;cin>>num;if(rank[num])nums.push_back(num);//沒有排名的數就不考慮了}int max_i[nums.size()]={0},max_res=0;for(int i=0;i<nums.size();i++){max_i[i]=1;for(int j=0;j<i;j++)//向前找最大的if(rank[nums[j]]<=rank[nums[i]])max_i[i]=max(max_i[i],max_i[j]+1);max_res=max(max_i[i],max_res);}cout<<max_res<<endl;return 0; }

總結

以上是生活随笔為你收集整理的PAT甲级-1045 Favorite Color Stripe (30分)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。