正文
【BZOJ-1260】涂色paint 区间DP
小程序：扫一扫查出行【扫一扫了解最新限行尾号】
复制小程序
1260: [CQOI2007]涂色paint
Time Limit: 30 Sec Memory Limit: 64 MB
Submit: 1147 Solved: 698
[Submit][Status][Discuss]
Description假设你有一条长度为5的木版，初始时没有涂过任何颜色。你希望把它的5个单位长度分别涂上红、绿、蓝、绿、红色，用一个长度为5的字符串表示这个目标：RGBGR。 每次你可以把一段连续的木版涂成一个给定的颜色，后涂的颜色覆盖先涂的颜色。例如第一次把木版涂成RRRRR，第二次涂成RGGGR，第三次涂成RGBGR，达到目标。 用尽量少的涂色次数达到目标。Input输入仅一行，包含一个长度为n的字符串，即涂色目标。字符串中的每个字符都是一个大写字母，不同的字母代表不同颜色，相同的字母代表相同颜色。Output仅一行，包含一个数，即最少的涂色次数。Sample InputSample Output【样例输入1】
AAAAA【样例输入1】
RGBGR
【样例输出1】
1
【样例输出1】
3
HINT40%的数据满足：1<=n<=10
100%的数据满足：1<=n<=50
SourceSolution
输入仅一行，包含一个长度为n的字符串，即涂色目标。字符串中的每个字符都是一个大写字母，不同的字母代表不同颜色，相同的字母代表相同颜色。
Output仅一行，包含一个数，即最少的涂色次数。Sample InputSample Output【样例输入1】
AAAAA【样例输入1】
RGBGR
【样例输出1】
1
【样例输出1】
3
HINT40%的数据满足：1<=n<=10
100%的数据满足：1<=n<=50
SourceSolution
Sample Output【样例输入1】
AAAAA【样例输入1】
RGBGR
【样例输出1】
1
【样例输出1】
3
HINT40%的数据满足：1<=n<=10
100%的数据满足：1<=n<=50
SourceSolution
AAAAA
【样例输入1】
RGBGR
【样例输出1】
1
【样例输出1】
3
40%的数据满足：1<=n<=10
100%的数据满足：1<=n<=50
SourceSolution
一道比较简单的区间DP
因为是区间涂色，如果s[l]=s[r]那么我们显然可以用一次覆盖[l,r]，然后中间的再另外考虑.
f[l][r]表示使[l,r]成为规定颜色的最小次数。
转移就是$f[l][r]=\begin{Bmatrix}min(f[l+r][r],f[l][r-1])&&&&s[l]=s[r]\\ min(f[l][r],f[l][k]+f[k+1][r])&&&&s[l]!=s[r]\end{Bmatrix}$
Code#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAXN 110
char s[MAXN];
int f[MAXN][MAXN],N,l,r;
int main()
{
scanf("%s",s+);
N=strlen(s+);
memset(f,,sizeof(f));
for (int i=; i<=N; i++) f[i][i]=;
for (int i=; i<=N; i++)
for (int j=; j+i<=N; j++)
{
l=j,r=j+i;
if (s[l]==s[r]) f[l][r]=min(f[l+][r],f[l][r-]);
else for (int k=l; k<=r-; k++) f[l][r]=min(f[l][r],f[l][k]+f[k+][r]);
}
printf("%d\n",f[][N]);
return ;
}
【BZOJ-1260】涂色paint 区间DP的更多相关文章- BZOJ 1260: [CQOI2007]涂色paint( 区间dp )
区间dp.. dp( l , r ) 表示让 [ l , r ] 这个区间都变成目标颜色的最少涂色次数. 考虑转移 : l == r 则 dp( l , r ) = 1 ( 显然 ) s[ l ] = ...
- [BZOJ1260][CQOI2007]涂色paint 区间dp
1260: [CQOI2007]涂色paint Time Limit: 30 Sec Memory Limit: 64 MB Submit: 1575 Solved: 955 [Submit][S ...
- 【bzoj1260】[CQOI2007]涂色paint 区间dp
题目描述 给出一个序列,每次可以给一段染成同一种颜色,问最少要染多少次能够染成给定方案. 输入 输入仅一行,包含一个长度为n的字符串,即涂色目标.字符串中的每个字符都是一个大写字母,不同的字母代表不同 ...
- B1260 [CQOI2007]涂色paint 区间dp
这个题和我一开始想的区别不是很大,但是要我独自做出来还是有一些难度. 每一次涂色 只有这两种可能: 1) 把一段未被 覆盖过的区间 涂成 * 色 2) 把一段被一种颜色覆盖的区间涂成 * 色 (并且 ...
- CQOI2007 涂色 paint (区间dp)
听说这道题是当年省选题 于是兴致勃勃拿来做了做 至于如何想到思路... 事实上没想象中那么简单... 脑阔挺疼的... (一开始都没看出来是区间dp) 想到可以区间dp,然后就似乎没啥大问题 枚举区间 ...
- 1260. [CQOI2007]涂色【区间DP】
Description 假设你有一条长度为5的木版,初始时没有涂过任何颜色.你希望把它的5个单位长度分别涂上红.绿.蓝.绿.红色,用一个长度为5的字符串表示这个目标:RGBGR. 每次你可以把一段连续 ...
- bzoj 1260涂色 题解
题面 区间dp, 我学的也不怎么好. myj说动态规划就是搜索的无限剪枝. 所以是搜了网上的代码, 看了看. 思路就是枚举区间,f数组就是存储从i到j需要的最少次数, 当然一开始他们的值要先设置一个很 ...
- [BZOJ 1260][CQOI2007]涂色paint 题解（区间DP）
[BZOJ 1260][CQOI2007]涂色paint Description 假设你有一条长度为5的木版,初始时没有涂过任何颜色.你希望把它的5个单位长度分别涂上红.绿.蓝.绿.红色,用一个长度为 ...
- 【DP】BZOJ 1260: [CQOI2007]涂色paint
1260: [CQOI2007]涂色paint Time Limit: 30 Sec Memory Limit: 64 MBSubmit: 893 Solved: 540[Submit][Stat ...
随机推荐- Twitter Snowflake 的Java实现
在关闭显示的情况下, 可以达到每毫秒3万个的生成速度 /** * An Implementation of Twitter Snowflake ID Generator */ public class ...
- win7 IIS7.5配置伪静态
转自:http://www.cnblogs.com/luckly-hf/archive/2013/03/07/2947687.html 第一部: 从如下地址中下载URLRewriter组件组件: 官方 ...
- 黑暗圣经---物业公司CTO/CEO改如何给老板推荐物业信息化产品
多年前一次偶然的机会进入到物业信息化行业,在这个过程中认识很多奋战在物业一线的技术大牛.很多时候都会介绍一些朋友给我认识一下,帮我推荐一下我们闻风多奇的物业管理平台.很多朋友看完我们的系统之后都会很开 ...
- C#.NET 大型通用信息化系统集成快速开发平台 4.0 版本 - 导入导出Microsoft Excel 2010的例子
1:能支持多种Excel版本,早期的.现在的版本都支持.2:能导入.3:能导出.4:有简单的例子可以参考.
- Silverlight调用本机exe程序
要点: 1. Silverlight必须启用OOB模式,以及 Require elevated trust when running in-browser.参考下图设置 注:OOB模式,并不意味着必须 ...
- java:使用匿名类直接new接口
java中的匿名类有一个倍儿神奇的用法,见下面代码示例: package contract; public interface ISay { void sayHello(); } 上面是一个简单的接口 ...
- 关于printf函数的所思所想
缘起大一下学期,C语言程序设计徐小青老师的随口一提,经娄嘉鹏老师提醒,我觉得应该自己整理清楚这一问题.涉及网上资料将会标明出处. 关于printf函数的所思所想 * printf的定义 printf( ...
- CAP原理的证明
CAP概述 C: Consistency 一致性 A: Availability 可用性 P:Partition Tolerance分区容错性 CAP理论的核心是:一个分布式系统不可能同时很好的满足一 ...
- 深入理解计算机系统（1.2）---hello world的程序是如何运行的
在写本章的内容之前,LZ先做个小广告.其实也不算是什么广告,就是LZ为了和各位猿友交流方便,另外也确实有个别猿友留言或者在博客里发短消息给LZ要联系方式.因此LZ斗胆建立了一个有关<深入理解计算 ...
- 开发WP版本的大菠萝英雄榜
前言 想当年Team有无数人在玩大菠萝,我被忽悠进来做肉盾,选了蛮子,从1.0开始,经历了103.105.108.2.0.2.1.这个游戏对我最大的帮助是学习了不同的技术,比如XAML.比如xcode ...
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAXN 110
char s[MAXN];
int f[MAXN][MAXN],N,l,r;
int main()
{
scanf("%s",s+);
N=strlen(s+);
memset(f,,sizeof(f));
for (int i=; i<=N; i++) f[i][i]=;
for (int i=; i<=N; i++)
for (int j=; j+i<=N; j++)
{
l=j,r=j+i;
if (s[l]==s[r]) f[l][r]=min(f[l+][r],f[l][r-]);
else for (int k=l; k<=r-; k++) f[l][r]=min(f[l][r],f[l][k]+f[k+][r]);
}
printf("%d\n",f[][N]);
return ;
}
- BZOJ 1260: [CQOI2007]涂色paint( 区间dp )
区间dp.. dp( l , r ) 表示让 [ l , r ] 这个区间都变成目标颜色的最少涂色次数. 考虑转移 : l == r 则 dp( l , r ) = 1 ( 显然 ) s[ l ] = ...
- [BZOJ1260][CQOI2007]涂色paint 区间dp
1260: [CQOI2007]涂色paint Time Limit: 30 Sec Memory Limit: 64 MB Submit: 1575 Solved: 955 [Submit][S ...
- 【bzoj1260】[CQOI2007]涂色paint 区间dp
题目描述 给出一个序列,每次可以给一段染成同一种颜色,问最少要染多少次能够染成给定方案. 输入 输入仅一行,包含一个长度为n的字符串,即涂色目标.字符串中的每个字符都是一个大写字母,不同的字母代表不同 ...
- B1260 [CQOI2007]涂色paint 区间dp
这个题和我一开始想的区别不是很大,但是要我独自做出来还是有一些难度. 每一次涂色 只有这两种可能: 1) 把一段未被 覆盖过的区间 涂成 * 色 2) 把一段被一种颜色覆盖的区间涂成 * 色 (并且 ...
- CQOI2007 涂色 paint (区间dp)
听说这道题是当年省选题 于是兴致勃勃拿来做了做 至于如何想到思路... 事实上没想象中那么简单... 脑阔挺疼的... (一开始都没看出来是区间dp) 想到可以区间dp,然后就似乎没啥大问题 枚举区间 ...
- 1260. [CQOI2007]涂色【区间DP】
Description 假设你有一条长度为5的木版,初始时没有涂过任何颜色.你希望把它的5个单位长度分别涂上红.绿.蓝.绿.红色,用一个长度为5的字符串表示这个目标:RGBGR. 每次你可以把一段连续 ...
- bzoj 1260涂色 题解
题面 区间dp, 我学的也不怎么好. myj说动态规划就是搜索的无限剪枝. 所以是搜了网上的代码, 看了看. 思路就是枚举区间,f数组就是存储从i到j需要的最少次数, 当然一开始他们的值要先设置一个很 ...
- [BZOJ 1260][CQOI2007]涂色paint 题解（区间DP）
[BZOJ 1260][CQOI2007]涂色paint Description 假设你有一条长度为5的木版,初始时没有涂过任何颜色.你希望把它的5个单位长度分别涂上红.绿.蓝.绿.红色,用一个长度为 ...
- 【DP】BZOJ 1260: [CQOI2007]涂色paint
1260: [CQOI2007]涂色paint Time Limit: 30 Sec Memory Limit: 64 MBSubmit: 893 Solved: 540[Submit][Stat ...
随机推荐- Twitter Snowflake 的Java实现
在关闭显示的情况下, 可以达到每毫秒3万个的生成速度 /** * An Implementation of Twitter Snowflake ID Generator */ public class ...
- win7 IIS7.5配置伪静态
转自:http://www.cnblogs.com/luckly-hf/archive/2013/03/07/2947687.html 第一部: 从如下地址中下载URLRewriter组件组件: 官方 ...
- 黑暗圣经---物业公司CTO/CEO改如何给老板推荐物业信息化产品
多年前一次偶然的机会进入到物业信息化行业,在这个过程中认识很多奋战在物业一线的技术大牛.很多时候都会介绍一些朋友给我认识一下,帮我推荐一下我们闻风多奇的物业管理平台.很多朋友看完我们的系统之后都会很开 ...
- C#.NET 大型通用信息化系统集成快速开发平台 4.0 版本 - 导入导出Microsoft Excel 2010的例子
1:能支持多种Excel版本,早期的.现在的版本都支持.2:能导入.3:能导出.4:有简单的例子可以参考.
- Silverlight调用本机exe程序
要点: 1. Silverlight必须启用OOB模式,以及 Require elevated trust when running in-browser.参考下图设置 注:OOB模式,并不意味着必须 ...
- java:使用匿名类直接new接口
java中的匿名类有一个倍儿神奇的用法,见下面代码示例: package contract; public interface ISay { void sayHello(); } 上面是一个简单的接口 ...
- 关于printf函数的所思所想
缘起大一下学期,C语言程序设计徐小青老师的随口一提,经娄嘉鹏老师提醒,我觉得应该自己整理清楚这一问题.涉及网上资料将会标明出处. 关于printf函数的所思所想 * printf的定义 printf( ...
- CAP原理的证明
CAP概述 C: Consistency 一致性 A: Availability 可用性 P:Partition Tolerance分区容错性 CAP理论的核心是:一个分布式系统不可能同时很好的满足一 ...
- 深入理解计算机系统（1.2）---hello world的程序是如何运行的
在写本章的内容之前,LZ先做个小广告.其实也不算是什么广告,就是LZ为了和各位猿友交流方便,另外也确实有个别猿友留言或者在博客里发短消息给LZ要联系方式.因此LZ斗胆建立了一个有关<深入理解计算 ...
- 开发WP版本的大菠萝英雄榜
前言 想当年Team有无数人在玩大菠萝,我被忽悠进来做肉盾,选了蛮子,从1.0开始,经历了103.105.108.2.0.2.1.这个游戏对我最大的帮助是学习了不同的技术,比如XAML.比如xcode ...
在关闭显示的情况下, 可以达到每毫秒3万个的生成速度 /** * An Implementation of Twitter Snowflake ID Generator */ public class ...
转自:http://www.cnblogs.com/luckly-hf/archive/2013/03/07/2947687.html 第一部: 从如下地址中下载URLRewriter组件组件: 官方 ...
多年前一次偶然的机会进入到物业信息化行业,在这个过程中认识很多奋战在物业一线的技术大牛.很多时候都会介绍一些朋友给我认识一下,帮我推荐一下我们闻风多奇的物业管理平台.很多朋友看完我们的系统之后都会很开 ...
1:能支持多种Excel版本,早期的.现在的版本都支持.2:能导入.3:能导出.4:有简单的例子可以参考.
要点: 1. Silverlight必须启用OOB模式,以及 Require elevated trust when running in-browser.参考下图设置 注:OOB模式,并不意味着必须 ...
java中的匿名类有一个倍儿神奇的用法,见下面代码示例: package contract; public interface ISay { void sayHello(); } 上面是一个简单的接口 ...
缘起大一下学期,C语言程序设计徐小青老师的随口一提,经娄嘉鹏老师提醒,我觉得应该自己整理清楚这一问题.涉及网上资料将会标明出处. 关于printf函数的所思所想 * printf的定义 printf( ...
CAP概述 C: Consistency 一致性 A: Availability 可用性 P:Partition Tolerance分区容错性 CAP理论的核心是:一个分布式系统不可能同时很好的满足一 ...
在写本章的内容之前,LZ先做个小广告.其实也不算是什么广告,就是LZ为了和各位猿友交流方便,另外也确实有个别猿友留言或者在博客里发短消息给LZ要联系方式.因此LZ斗胆建立了一个有关<深入理解计算 ...
前言 想当年Team有无数人在玩大菠萝,我被忽悠进来做肉盾,选了蛮子,从1.0开始,经历了103.105.108.2.0.2.1.这个游戏对我最大的帮助是学习了不同的技术,比如XAML.比如xcode ...
