首页 › 题库 › C/C++编程考级 › C/C++编程四级 › 简答题
简答题 偏难
#7557

彩带 织女要织一条自己最爱的彩带,方法是从一条现成的彩带上按照她喜欢的颜色顺序保留她最爱的几种颜色,裁掉不要的部分,把留下的缝制在一起,就制成了她最喜欢的彩带。…

彩带

织女要织一条自己最爱的彩带,方法是从一条现成的彩带上按照她喜欢的颜色顺序保留她最爱的几种颜色,裁掉不要的部分,把留下的缝制在一起,就制成了她最喜欢的彩带。

一般肉眼能分辨的颜色不超过 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 },长度都是 7。

时间限制:1000

内存限制:262144

输入

输入第一行给出一个正整数 N(≤ 200),为颜色种类的数量(即颜色从 1 到 N 编号)。下一行先给出一个正整数 M(≤ 200),随后是织女喜欢的 M个颜色,按她喜欢的顺序给出。第三行也是先给出一个正整数 L(≤ 104),即原始彩带的长度,随后是 L 个颜色值。一行中的所有数字以空格分隔。

输出

只需要输出织女最喜欢的彩带的最大长度值。


样例输入

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

样例输出

7
未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;iostream&gt; #include &lt;vector&gt; #include &lt;unordered_map&gt; using namespace std; int main() {     int N, M, L;     cin &gt;&gt; N; // 颜色总数,此处可忽略     // 读取织女喜欢的颜色序列     cin &gt;&gt; M;     vector&lt;int&gt; favorite(M);     for (int i = 0; i &lt; M; ++i) {         cin &gt;&gt; favorite[i];     }     // 建立颜色到位置的映射,记录每个颜色最后出现的位置     unordered_map&lt;int, int&gt; colorToPos;     for (int i = 0; i &lt; M; ++i) {         colorToPos[favorite[i]] = i + 1; // 位置从1开始     }     // 读取原始彩带并转换为有效的位置列表     cin &gt;&gt; L;     vector&lt;int&gt; positions;     for (int i = 0; i &lt; L; ++i) {         int color;         cin &gt;&gt; color;         if (colorToPos.count(color)) {             positions.push_back(colorToPos[color]);         }     }     // 动态规划处理     vector&lt;int&gt; currentMax(M + 1, 0); // currentMax[i]表示以位置i结尾的最长子序列长度     vector&lt;int&gt; prefixMax(M + 1, 0);  // prefixMax[i]表示前i个位置的最大长度     for (int p : positions) {         int newLen = prefixMax[p] + 1;         if (newLen &gt; currentMax[p]) {             currentMax[p] = newLen;             // 更新prefixMax数组             for (int i = 1; i &lt;= M; ++i) {                 if (i == 1) {                     prefixMax[i] = currentMax[i];                 } else {                     prefixMax[i] = max(prefixMax[i - 1], currentMax[i]);                 }             }         }     }     cout &lt;&lt; prefixMax[M] &lt;&lt; endl;     return 0; }</pre><p><br/></p>
解析

方法思路:

预处理织女喜欢的颜色序列:建立一个颜色到位置的映射,记录每个颜色在织女喜欢的序列中最后出现的位置。

过滤原始彩带:将原始彩带中的颜色转换为对应的位置,过滤掉不在织女喜欢的颜色序列中的颜色。

动态规划:维护两个数组,current_max 和 prefix_max。current_max 数组记录以每个位置结尾的最长子序列长度,prefix_max 数组记录前缀最大值。遍历处理后的位置列表,更新这两个数组,最终得到最长子序列的长度。