1045. Favorite Color Stripe (30)

拼搏现实的明天。 2022-05-31 12:50 159阅读 0赞

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 (<=10000) which is the length of the given stripe, followed by L colors on the stripe. All the numbers in a line are 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:**

--------------------

题目大意：

伊娃想从给定的颜色条中挑出他自己喜欢的颜色线条。他想只保留他喜欢的并按他喜欢的顺序的颜色，剪掉她不喜欢的颜色片，把剩下的缝在一起形成他喜欢的条文。  
据说正常人的眼睛能辨别不超过200不同的颜色，所以伊娃最喜欢的颜色是有限的。但是原始的条纹可能很长，伊娃想要剩余的最喜欢的条纹长度和最大。所以他需要你的帮助才能找到最好的结果。  
请注意，解决方案可能不是唯一的，但是你只需要告诉他最大长度。例如，给定一个颜色条纹\{2 2 4 1 5 5 6 3 1 1 5 6\}。如果伊娃最喜欢的颜色和他最喜欢的顺序为\{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\}。  
输入规范：  
每个输入文件包含一个测试用例。对于每个案例，第一行包含一个正整数N（<=200）表示颜色的总数（因此颜色的编号从1到N）。然后下一行开始一个正整数M(<=200),M是以伊娃喜欢的顺序给出的伊娃最喜欢的颜色。最后，以一个整数L（<=10000）开始，这是给定条纹的长度，后面是L个颜色。直线上得所有数字都用空格隔开。  
输出规范：

对于每个测试用例，只需将伊娃最喜欢的颜色条纹的最大长度打印在一行中即可。

注：此题是最长公共子序列的变形，详细请看：[点击打开链接][Link 1]

代码：

#include<stdio.h>
    int like[201];
    int give[10001];
    int len[201][10001];
    int main()
    {
        int i,j,n,m,k,t,Max;
        scanf("%d",&n);
        scanf("%d",&m);
        for(i=1;i<=m;i++)
        {
            scanf("%d",&like[i]);
        }
        scanf("%d",&k);
        for(i=1;i<=k;i++)
        {
            scanf("%d",&give[i]);
        }
        for(i=1;i<=m;i++)
        {
            for(j=1;j<=k;j++)
            {
                Max=len[i-1][j-1];
                if(Max<len[i][j-1])
                {
                    Max=len[i][j-1];
                }
                if(Max<len[i-1][j])
                {
                    Max=len[i-1][j];
                }
                if(like[i]==give[j])
                {
                    len[i][j]=Max+1;
                }
                else
                {
                  len[i][j]=Max;
                }
            }
        }
        printf("%d\n",len[m][k]);
        return 0;
    }

[Link 1]: http://blog.csdn.net/guoqingshuang/article/details/79368191