专栏首页vblogPAT1045 Favorite Color Stripe (30分) 动态规划

PAT1045 Favorite Color Stripe (30分) 动态规划

题目

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 (≤104​​ ) 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试着从给出的布条中选出她自己的彩色布条。她想要仅仅保留按照她最喜欢的顺序排列的她喜欢的颜色,并且剪掉那些不喜欢的部分再将剩下的部分缝在一起来组成她最喜欢的彩色布条。所以她需要你的帮助来找出最好的结果。

注意结果可能不唯一,但是你只需要告诉她最大的长度。举个例子,给你一个 {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}。(注意最喜欢的顺序排列 的每个数字都不重复)

解题报告:

  • 因为最喜欢的顺序排列的每个数字都不重复,也就是说我可以给这些数字重新定序(注意这个转换思路非常巧妙)book[i] = j表示在最喜欢的颜色排列中,颜色i的下标为j
  • 先在输入的时候剔除不在喜欢的序列中的元素(假如输入的是颜色k,查一下book[k]是否有效),然后我们直接在当前位置不保存颜色k,而是保存book[k],这样原输入数组每个位置代表的含义(本来是颜色i)就变成了颜色i在最喜欢的颜色中的下标。
  • 这样我们从中选取满足最喜欢顺序的片段,就转化为一个LIS(最长递增子序列)问题了,也就是从中找出最长的非递减子序列的长度,这样我们就可以用动态规划了(关于这个解法,推荐一篇博客,讲的非常清楚)。

代码

#include <iostream>
#include <vector>
using namespace std;


int main() {
    int n, m, x, l, num = 0, maxn = 0;
    // 原颜色条纹
    int stripe[10001];
    // 每个颜色在最喜欢颜色序列中的位置(唯一)
    int book[201];

    cin >> n >> m;
    // 初始化
    fill(book, book + 201, -1);

    // 输入最喜欢的颜色序列
    for (int i = 1; i <= m; ++i) {
        cin >> x;
        // 转成book[颜色]=下标
        book[x] = i;
    }
    // 输入l个条纹颜色
    cin >> l;
    for (int i = 1; i <= l; ++i) {
        cin >> x;
        // 取出无效的(不喜欢的部分)
        if (book[x] != -1) {
            // 把颜色转成当前颜色在最喜欢颜色中的位置
            stripe[++num] = book[x];
        }
    }
    // 动态规划求解最长连续递增序列
    // dp[i]表示从开始位置到当前位置的最长递增子序列的长度
    int dp[num + 1];
    for (int i = 1; i <= num; ++i) {
        // 从每个位置开始,最短序列长度是1(自身)
        dp[i] = 1;
        // 状态转移
        for (int j = 1; j < i; ++j) {
            if (stripe[j] <= stripe[i]) dp[i] = max(dp[i], dp[j] + 1);
        }
        // 保存其中最大的长度
        maxn = max(maxn, dp[i]);
    }

    // 输出最大值
    cout << maxn;

    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • PAT 1007 Maximum Subsequence Sum (25分) 最大连续子序列和

    Given a sequence of K integers { N​1​​ , N​2​​ , ..., N​K​​ }. A continuous subs...

    vivi
  • PAT 1017 Queueing at Bank (25分) prioriry_queue

    Suppose a bank has K windows open for service. There is a yellow line in front o...

    vivi
  • PAT 1015 Reversible Primes (20分) 谜一般的题目,不就是个进制转换+素数判断

    A reversible prime in any number system is a prime whose "reverse" in that numbe...

    vivi
  • CentOS 7下安装Python3.6

    yum install openssl-devel bzip2-devel expat-devel gdbm-devel readline-devel sqli...

    py3study
  • 网易互联网&网易游戏产品经理面试经验

    网易是分网易游戏和网易互联网的,本人都参加了校园招聘面试,最后均拿到了产品经理的offer。 网易是分网易游戏和网易互联网的,先说网易互联网吧,当时是去杭州总部...

    牛客网
  • 读取资源文件的四种方法

    package com.action; import java.io.InputStream; import java.util.Locale; import...

    小柒2012
  • 投行、学界和科技界的世界杯冠军预测大战

    从1998年的法国世界杯开始,知名投行高盛在世界杯之前都要发布一份关于世界杯经济学的投行报告,至今已经持续了 20 年,预测工具是一些基于经济统计学的数据工具。...

    HyperAI超神经
  • 全球首个AI合成主播发布,效果以假乱真!揭秘背后技术原理

    2016年,王小川在正式论坛里秀出AI同传,那是机器实时翻译技术,首次在高规格国际会议上实战应用。

    昱良
  • 全球首个AI合成主播发布,效果以假乱真!揭秘背后技术原理

    2016年,王小川在正式论坛里秀出AI同传,那是机器实时翻译技术,首次在高规格国际会议上实战应用。

    量子位
  • WinXP系统中的Oracle数据库如何以管理员身份登录

    打开命令行,输入:sqlplus sys/password as sysdba ,如下图所示:

    黑泽君

扫码关注云+社区

领取腾讯云代金券