首页 > 试题广场 >

[CQOI2007]涂色PAINT

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


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


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

输入

AAAAA

输出

1
示例2

输入

RGBGR

输出

3

备注:
40% 的数据满足 。

100% 的数据满足 。
算法知识视频讲解
添加回答
牛客HFL头像 牛客HFL
发表于 2023-07-26 17:28:25 回复(0)
Python3
不想上班艾伦是单身头像 不想上班艾伦是单身
import sys
num =[]
for line in sys.stdin:
    a = line.split()
    num.append(a)
try: 
    string= a[0]
except:
    string=num[0][0]

length = len(string)
dp = [[0]*(length+1) for i in range(length+1)]
for i in range(length):
    dp[i][i] = 1

for leng in range(1,length+1,1):
    for i in range(0,length-leng,1):
        ends = leng+i
        dp[i][ends] = float('inf')
        if string[i] == string[ends]:
            dp[i][ends] = min(dp[i+1][ends],dp[i][ends-1])
        for j in range(i,leng+i+1,1):
            dp[i][ends] = min(dp[i][ends],dp[i][j]+dp[j+1][ends])

print(dp[0][length-1])
发表于 2022-12-15 21:04:24 回复(1)
Python 3
牛客760622808号头像 牛客760622808号
补充一个python版本 
def ans():
    s = list(input())
    size = len(s)
    dp = [[float("inf")] * size for _ in range(size)]
    for l in range(size):
        for left in range(size):
            if l == 0:
                dp[left][left] = 1
                continue
            right = left + l 
            if right < size:
                if s[left] == s[right]:
                    dp[left][right] = min(dp[left+1][right],dp[left][right-1])
                else:
                    for mid in range(left,right):
                        dp[left][right] = min(dp[left][right], dp[left][mid] + dp[mid+1][right])
            else:
                break
    print(dp[0][size-1])
ans()


发表于 2021-11-03 22:44:39 回复(0)
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
难度：
4条回答 2173浏览

热门推荐

通过挑战的用户

查看代码

相关试题

[CQOI2007]涂色PAINT

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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