首页 > 试题广场 >

[CQOI2007]涂色PAINT

[编程题][CQOI2007]涂色PAINT
  • 热度指数：1983 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
假设你有一条长度为5的木版，初始时没有涂过任何颜色。你希望把它的5个单位长度分别涂上红、绿、蓝、绿、红色，用一个长度为5的字符串表示这个目标：RGBGR。 每次你可以把一段连续的木版涂成一个给定的颜色，后涂的颜色覆盖先涂的颜色。
例如第一次把木版涂成RRRRR，第二次涂成RGGGR，第三次涂成RGBGR，达到目标。 用尽量少的涂色次数达到目标。


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


输出描述:
仅一行，包含一个数，即最少的涂色次数。
示例1

输入

AAAAA

输出

1
示例2

输入

RGBGR

输出

3

备注:
40% 的数据满足 。

100% 的数据满足 。
算法知识视频讲解
添加回答
C
cs小白_头像 cs小白_ 
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <limits.h>
int min(int a,int b){
    return a>b?b:a;
}
int main()
{
    char c[100];
    scanf("%s",c);
    int len=strlen(c);
    int dp[len][len];
    for (int i=0; i<len; i++) {
        for (int j=0; j<len; j++) {
             dp[i][j]=INT_MAX;
        }
    }
    for (int l=1;l<=len; l++) {
         for (int i=0; i<len; i++) {
              int j=i+l-1;
              if (j>=len) {
                  break;
              }
              if (i==j) {
                  dp[i][j]=1;
                  continue;
              }
              if (c[i]==c[j]) {
                    dp[i][j]=min(dp[i+1][j],dp[i][j-1]);
              }
              else{
                for (int k=i; k<=j-1; k++) {
                      dp[i][j]=min(dp[i][j], dp[i][k]+dp[k+1][j]);
                }
              }
         }
    }
    printf("%d",dp[0][len-1]);
    return 0;
}

发表于 2024-12-03 10:38:26 回复(0)
提交观点

问题信息

区间dp
难度：
1条回答 2320浏览

热门推荐

通过挑战的用户

查看代码

相关试题

[CQOI2007]涂色PAINT

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号