【算法•日更•第三十期】区间动态规划：洛谷P4170 [CQOI2007]涂色题解

　　废话不多说，直接上题：

P4170 [CQOI2007]涂色

题目描述

假设你有一条长度为5的木版，初始时没有涂过任何颜色。你希望把它的5个单位长度分别涂上红、绿、蓝、绿、红色，用一个长度为5的字符串表示这个目标：RGBGR。

每次你可以把一段连续的木版涂成一个给定的颜色，后涂的颜色覆盖先涂的颜色。例如第一次把木版涂成RRRRR，第二次涂成RGGGR，第三次涂成RGBGR，达到目标。

用尽量少的涂色次数达到目标。

输入格式

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

输出格式

仅一行，包含一个数，即最少的涂色次数。

输入输出样例

输入 #1

AAAAA

输出 #1

输入 #2

RGBGR

输出 #2

说明/提示

40%的数据满足：1<=n<=10

100%的数据满足：1<=n<=50

　　首先，我们先来看一下样例，就以样例二为例子讲解吧，应该是红、绿、蓝、绿、红的样子，也就是说目标样子是这样的：

　　那么我们是如何涂的呢?

　　首先是红色：

　　然后是绿色：

　　最后是蓝色：

　　一共是3次，当然，也有其他涂法，不过都是三次。

　　那么我们可以先来思考，每次我们刷的是什么？一个区间！显然，答案就是整个区间，像极了区间动态规划，那么我们就使用区间动态规划的思路来解吧。

　　设计状态自然是不难的，我们用f[i][j]表示i～j区间内变成目标状态刷的次数。

　　关键所在是状态转移方程，先来思考一个区间左右两端的颜色可能是什么关系？

　　①相同的：那么就是说我们只要这个区间直接刷上这个颜色，那么其中一个端点就是白刷的，因为没有特地的去刷它，那就不管其中一个点了，那么我们就只要把问题抛给f[i+1][j]和f[i][j-1]就可以了。

　　②不同的：我们直接把问题抛给f[i][k]+f[k+1][j]就好了。

　　这样两个状态转移方程就列好了f[i][j]=min(f[i+1][j],f[i][j-1])和f[i][j]=min{f[i][k]+f[k+1][j]}。

　　直接看代码吧：

 #include<iostream>

 #include<cstring>

 using namespace std;

 int f[][];

 char s[];

 int main()

 {

     cin>>s+;//从1开始

     int n=strlen(s+);

     memset(f,0x3f3f3f3f,sizeof(f));//赋初始值

     for(int i=;i<=n;i++) f[i][i]=;//给一个地方刷当然是刷一次

     for(int l=;l<n;l++)//以下是区间dp模板

     for(int i=,j=l+;j<=n;i++,j++)

     {

             if(s[i]==s[j]) //分情况：首尾颜色一样

             f[i][j]=min(f[i+][j],f[i][j-]);

             else//不一样

             {

                 for(int k=i;k<j;k++)

                 f[i][j]=min(f[i][j],f[i][k]+f[k+][j]);

             }

     }

     cout<<f[][n];

     return ;

 }