PAT甲级——A1045 Favorite Color Stripe-白红宇

PAT甲级——A1045 Favorite Color Stripe

阅读量：4541 次

发布时间：2019-06-08

本文共 3317 字，大约阅读时间需要 11 分钟。

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

Output Specification:

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

Sample Input:

65 2 3 1 5 612 2 2 4 1 5 5 6 3 1 1 5 6

Sample Output:

LIS——最长不下降子序列：

算法设计

定义一个长度为N的order数组，将Eva喜欢的颜色编号作为下标，对应元素为次序编号，例如给定喜欢的颜色为2 3 1 5 6，那么order[2]=1,order[3]=2……定义数组A存储给定的珠子序列，定义一个数组dp，其中dp[i]表示以 A[i]结尾的符合要求的子序列最长长度。那么对于0<=i<N，找出0<=j<i之间满足order[i]>=order[j]的最大的dp元素值MAX，则dp[i]=max(MAX,1)。遍历dp数组找出最大的值即为所求。

1 using namespace std; 2 int main(){ 3     int N,M,L,a; 4     scanf("%d%d",&N,&M); 5     int order[N+1]={
   0}; 6     for(int i=1;i<=M;++i){
   //给order数组赋值 7         scanf("%d",&a); 8         order[a]=i; 9     }10     scanf("%d",&L);11     int A[L],maxLen=0,dp[L]={
   0};12     for(int i=0;i
     
      0){
   //是喜欢的颜色16             int MAX=0;17             for(int j=0;j
      
       =order[j]的最大的dp值18                 if(order[A[i]]>=order[A[j]])19                     MAX=max(dp[j],MAX);20             dp[i]=max(MAX+1,1);//更新dp数组值21             maxLen=max(maxLen,dp[i]);//更新最大长度22         }23     }24     printf("%d",maxLen);25     return 0;26 }

LCS——最长公共子序列

算法设计

定义一个数组A储存喜欢的颜色编号序列，定义一个数组B存储给定的一串珠子序列，找出A、B之间的最长公共子序列即可。由于颜色可以重复，即子序列中可以有重复元素，状态转移方程为：

如果A[i]==B[j]，

如果A[i]!=B[j]，

边界情况为：

dp[i][0]=dp[0][j]=0(0<=i<=M,0<=j<=L)

1 using namespace std; 2 int dp[205][10005]; 3 int main(){ 4     int N,M,L; 5     scanf("%d%d",&N,&M); 6     int A[M+1]={
   0}; 7     for(int i=1;i<=M;++i) 8         scanf("%d",&A[i]); 9     scanf("%d",&L);10     int B[L+1]={
   0};11     for(int i=1;i<=L;++i)12         scanf("%d",&B[i]);13     for(int i=1;i<=M;++i)14         for(int j=1;j<=L;++j)15             if(A[i]==B[j])16                 dp[i][j]=max(dp[i][j-1],dp[i-1][j-1])+1;17             else18                 dp[i][j]=max(dp[i][j-1],dp[i-1][j]);19     printf("%d",dp[M][L]);20     return 0;21 }

转载于:https://www.cnblogs.com/zzw1024/p/11273153.html

你可能感兴趣的文章