P4170 [CQOI2007]涂色

    • 623通过
    • 1.3K提交
  • 题目提供者 Fee_cle6418
  • 评测方式 云端评测
  • 标签 区间动规,区间dp 字符串 枚举,暴力 各省省选 2007 重庆
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    假设你有一条长度为5的木版,初始时没有涂过任何颜色。你希望把它的5个单位长度分别涂上红、绿、蓝、绿、红色,用一个长度为5的字符串表示这个目标:RGBGR。

    每次你可以把一段连续的木版涂成一个给定的颜色,后涂的颜色覆盖先涂的颜色。例如第一次把木版涂成RRRRR,第二次涂成RGGGR,第三次涂成RGBGR,达到目标。

    用尽量少的涂色次数达到目标。

    输入输出格式

    输入格式:

    输入仅一行,包含一个长度为n的字符串,即涂色目标。字符串中的每个字符都是一个大写字母,不同的字母代表不同颜色,相同的字母代表相同颜色。

    输出格式:

    仅一行,包含一个数,即最少的涂色次数。

    输入输出样例

    输入样例#1: 复制
    AAAAA
    输出样例#1: 复制
    1
    输入样例#2: 复制
    RGBGR
    输出样例#2: 复制
    3

    说明

    40%的数据满足:1<=n<=10

    100%的数据满足:1<=n<=50

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。