BZOJ1260 CQOI2007 涂色paint 【区间DP】
2024-08-29 15:54:26
BZOJ1260 CQOI2007 涂色paint
Description
假设你有一条长度为5的木版,初始时没有涂过任何颜色。你希望把它的5个单位长度分别涂上红、绿、蓝、绿、红色,用一个长度为5的字符串表示这个目标:RGBGR。 每次你可以把一段连续的木版涂成一个给定的颜色,后涂的颜色覆盖先涂的颜色。例如第一次把木版涂成RRRRR,第二次涂成RGGGR,第三次涂成RGBGR,达到目标。 用尽量少的涂色次数达到目标。
Input
输入仅一行,包含一个长度为n的字符串,即涂色目标。字符串中的每个字符都是一个大写字母,不同的字母代表不同颜色,相同的字母代表相同颜色。
Output
仅一行,包含一个数,即最少的涂色次数。
Sample Input
Sample Output
【样例输入1】
AAAAA
【样例输入1】
RGBGR
【样例输出1】
1
【样例输出1】
3
HINT
40%的数据满足:1<=n<=10
100%的数据满足:1<=n<=50
暴搜的范围,然而却是区间DP
考虑dpi,j表示把区间[l,r]染成目标状态的最小次数
首先我们判断一下al是不是等于ar,如果是的话可以从
min(dp{l,r−1},dp{l+1,r},dp{l+1,r−1}+1)转移的
然后再枚举中间的分界点mid
判断一下a_mid是不是等于a_mid+1
是的话可以从dp{l,mid}+dp{mid+1,r−1}转移
否则可以从dp{l,mid}+dp{mid+1,r}转移
#include<bits/stdc++.h>
using namespace std;
#define N 60
int dp[N][N],n;
char a[N];
int main(){
memset(dp,0x3f,sizeof(dp));
scanf("%s",a+);
n=strlen(a+);
if(n==){printf("");return ;}
for(int i=;i<=n;i++)dp[i][i]=;
for(int len=;len<=n;len++)
for(int l=;l+len-<=n;l++){
int r=l+len-;
if(a[l]==a[r]){
dp[l][r]=min(dp[l][r-],dp[l+][r]);
dp[l][r]=min(dp[l][r],dp[l+][r-]+);
}
for(int mid=l;mid<r;mid++){
if(a[mid]==a[mid+])dp[l][r]=min(dp[l][r],dp[l][mid]+dp[mid+][r]-);
else dp[l][r]=min(dp[l][r],dp[l][mid]+dp[mid+][r]);
}
}
printf("%d",dp[][n]);
return ;
}
最新文章
- [译]ZOOKEEPER RECIPES-Locks
- occ代码分析
- C#基础总结
- MongoDB的基础知识
- 猿题库 iOS 客户端架构设计
- android-数据存储之远程服务器存储
- Golang gRPC 示例
- not use jquery
- php中include包含文件路径查找过程
- flexPaper +swftools实现文档在线阅读
- 金蝶盘点机条码数据採集器PDA,WIFI已经连接,可是PDA应用程序还是网络初始化不成功?
- Perl语言学习笔记 9 正则表达式处理文本
- Codeforces Round #269 (Div. 2) A B C
- MYSQL 主从服务器配置工作原理
- 每次启动懂maven项目都必须关闭javaw.exe进程
- JAVA集合1--总体框架
- 解决vscode更新后Ext Js插件无法使用问题
- Windows 服务器自动重启定位
- golang web framework--Martini
- 二、存储管理器--SDRAM