【题解】 bzoj1260: [CQOI2007]涂色paint （区间dp）

首页 > 【题解】 bzoj1260: [CQOI2007]涂色paint （区间dp）

【题解】 bzoj1260: [CQOI2007]涂色paint （区间dp）

bzoj1260，懒得复制，戳我戳我

Solution:

~~这种题目我不会做qwq，太菜了~~

区间打牌~~(dp)~~

用f[l][r]表示从l到r最少需要染几次色。
状态转移方程：

1.(f[l][r]=min(f[l][i],f[i+1][r]) (l<=i 这段染色等于俩段分别染色，很好看出来。

2.(if(s[l]==s[r]) f[l][r]=min(min(f[l+1][r],f[l][r+1]),f[l+1][r-1]))。
分俩种一可以直接涂上俩端点，2是可以忽略掉左端点和右端点。
第2点作用是很关键的，它会解决类似(ABACDA)之类的问题。忽略掉一段端点之后就可以继续找俩个端点进行染色。
为什么是对的呢？因为最后无论如何都一个节点都需要涂一次，所有的同色的端点就也被涂了。

转载的博客

Code:

//It is coded by Ning_Mew on 5.22
#include
using namespace std;const int maxn=55;int n;
string s;
int dp[maxn][maxn];int main(){cin>>s;n=s.length();memset(dp,0x5f,sizeof(dp));for(int i=0;i

 
转载于:https://www.cnblogs.com/Ning-Mew/p/9072844.html


            
                
                    更多相关：
                    
                        
                    
                        剑指offer：面试题19. 正则表达式匹配
                    
                    
                        
                            题目：正则表达式匹配 
请实现一个函数用来匹配包含'. '和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但与"aa.a"和"ab*a"均不匹配。 
示例 1:...
                            
                        
                    
				

                    
                        BZOJ 1801 [Ahoi2009]中国象棋（线性动规）（洛谷P2051）
                    
                    
                        
                            题意：就是在n*m的格子中放“炮”（中国象棋中的棋子）问有多少种放法，使得没有任意的两个炮相互攻击 思路：我们很容易的得到一列或者一行中最多放下两个炮（我也只能得到这些了，满脑子状压，但数据范围有100），这篇博客些的很好（传送门），我们定义dp[i][j][k]代表前i行我们有j列式有2个棋子，有k列是一个棋子，那么我们空的列的个数...
                            
                        
                    
				

                    
                        【洛谷习题】小A点菜
                    
                    
                        
                            虽然也是一道dp的入门题，但就是想不到，或者说不会实现。dp还是要多做题。 链接：https://www.luogu.org/problemnew/show/P1164   我们可以设dp[i][j]表示以考虑完第i件，恰好消费j元的方案数。那么dp[i][j]=dp[i-1][j]+dp[i-1][j-a[i]]，也就是讨论第i件点...
                            
                        
                    
				

                    
                        模拟城市2.0
                    
                    
                        
                            题目背景 博弈正在机房颓一个叫做《模拟城市2.0》的游戏。 2048年，经过不懈努力，博弈终于被组织委以重任，成为D市市委书记！他勤学好问，励精图治，很快把D市建设成富强民主文明和谐的美好城市。为了进一步深化发展，他决定在海边建立一个经济开发区。 题目描述 已知开发区的建筑地块是一个n×nn 	imes nn×n的矩形，而开发...
                            
                        
                    
				

                    
                        leecode第二十题（有效的括号）
                    
                    
                        
                               class Solution {
public:bool isValid(string s) {int start=0,end=s.size()-1;if(end==-1)//万万没想到，他把空字符串当成true了return true;int ss[end+1];//歪方法，把左括号全部<0，右括号都>0，且同类型符号绝对值...