noip题解|区间dp--P4170 [CQOI2007]涂色
传送门
题目描述
假设你有一条长度为5的木版,初始时没有涂过任何颜色。你希望把它的5个单位长度分别涂上红、绿、蓝、绿、红色,用一个长度为5的字符串表示这个目标:RGBGR。
每次你可以把一段连续的木版涂成一个给定的颜色,后涂的颜色覆盖先涂的颜色。例如第一次把木版涂成RRRRR,第二次涂成RGGGR,第三次涂成RGBGR,达到目标。
【noip题解|区间dp--P4170 [CQOI2007]涂色】用尽量少的涂色次数达到目标。
输入格式
输入仅一行,包含一个长度为n的字符串,即涂色目标。字符串中的每个字符都是一个大写字母,不同的字母代表不同颜色,相同的字母代表相同颜色。
输出格式
仅一行,包含一个数,即最少的涂色次数。
输入输出样例
输入 #1 复制
AAAAA
输出 #1 复制
1
输入 #2 复制
RGBGR
输出 #2 复制
3
说明/提示
40%的数据满足:1<=n<=10
100%的数据满足:1<=n<=50
题解
1.本题题意:区间内的涂色次数。这很明显!–区间dp。
状态很好定义,就是f[i][j]表示从i到j的涂色次数。
2.需要注意的是,本题要求的是最优解,但是涂色是以区间的形式,那么如果区间两端要求涂的颜色相同,就可以直接从两个子区间转移过来。
如下
if(vi[i]==vi[j])
{
f[i][j]=min(f[i][j],f[i+1][j]);
f[i][j]=min(f[i][j],f[i][j-1]);
}
3.初始化每个区间长度为1的区间最小值都应该是1
4.状态转移方程,直接在i到j之间枚举一个k就行:
for(int k=i;
k
5.附上AC代码+注释
#include
#include
#include
#include
#define maxn 105
using namespace std;
char vi[maxn];
int len=0;
int f[maxn][maxn];
int main()
{ cin>>vi;
len=strlen(vi);
memset(f,0x3f,sizeof(f));
for(int i=0;
i
推荐阅读
- ACSL|ACSL 美国计算机科学联赛 2016-2017 R4 摩天大楼-Skyscraper 题解
- dCas9技术流程与实验问题解决方案
- 【JS 逆向百例】吾爱破解2022春节解题领红包之番外篇 Web 中级题解
- 用周期思维淡定面对下行区间
- 环境安装部署|Anaconda 中升级Python到高版本以及 Solving environment问题解决
- arcgis属性表出现中文乱码问题解决
- SwiftUI|SwiftUI iOS 组件之双值区间取值选择器RangeSlider支持颜色(教程含源码)
- leetcode题解|leetcode#106. 从中序与后序遍历序列构造二叉树
- 网络爬虫抓取图片并上传到fastdfs图片不完整问题解决
- anaconda3之基本使用、更换国内镜像、安装python虚拟器、第三方库安装及问题解决