题解 P4170 【[CQOI2007]涂色】

dzz1537568241 · 2019-08-26 15:11:10 · 题解

区间dp万岁！

• 如果你不知道什么叫区间dp的话，移步 区间dp模板：石子合并

• 如果会区间dp ， 但依然弄不懂大佬们是怎么想出这道题的，先看代码，尝试理解一下

• 如果你懒到代码都不想看的话，稍微注意一下状态转移方程式，确保你有印象

  #include <iostream>
  #include <cstring> 
  #define INF 0x3f3f3f
  using namespace std;
  int N;
  int f[52][52];
  string a;
  int main(){
  cin>>a;
  N = a.size();
  //分为两种情况讨论：
  
  //如果左右端点相等的话，那么相当于免费涂一个
  
  //状态转移方程式：f[i][j]=min(f[i+1][j],f[i][j-1])
  
  //如果左右端点不相等的话，直接把两个区间相加即可 
  
  //状态转移方程式:f[i][j]=min(f[i][j],f[i][k] + f[k + 1][j]); 
  
      memset(f,INF,sizeof(f));
  for(int i = 1;i <= N;i++){
      f[i][i] = 1;
  }
  for(int len = 2; len <= N; len++){
      for(int i = 1; i <= N - len + 1; i++){
          int head = i, tail = i + len - 1;
          if(a[head-1] == a[tail-1]){
                  f[head][tail]=min(f[head + 1][tail],f[head][tail-1]);
                  continue;
          }
          for(int k = head; k <= tail; k++){
              f[head][tail]=min(f[head][k] + f[k+1][tail],f[head][tail]);
          }
      }
  }
  cout<<f[1][N];
  } 

  1.确定区间dp

• 仔细观察每一次染色的操作对象，是一个连续的范围，这是区间dp最明显的特征, 确定算法核心是区间dp

2.纸上模拟

• 确定是区间dp之后，第一步是在纸上画上一条数轴

• 由于区间dp的核心思想是由一个个小区间进行合并成为大区间，我们应该先模拟长度最小的，即长度为1的区间

• 数轴更好的帮助你理解，在研究长度为n的区间的时候可以在数轴上标明覆盖区间，这样非常直观

• 以这道题目为例子

  • 长度为1的区间的值很好求，涂色次数就是1

  • 长度为2的区间的值...嗯需要想一想，是由两个长度为1的区间进行合并，

    1. 如果两个区间的颜色相同，次数 = 其中一个长度为1的区间

    2. 如果两个区间的颜色不相同，次数 = 两个长度为1的区间涂色次数之和

  • 长度为3的区间的值，由一个长度为2的区间 + 一个长度为1的区间合并

    • 合并3的时候就要开始思考状态转移方程式了！！！

    • 这里数轴就有用处了，请肆意践踏你的数轴，标明各种情况，思考不同情况下需要写出的状态转移方程式

    • 设此时研究的区间左右端点为 i , i + 2

  1. a 是题目给的字符串，

  a[i] = a[i + 1]，则
  
      f[i][i+2] = f[i+1][i+2]
  
  （长度为 1 的被合并在长度为 2 的那一刷子里）

• 等等，似乎这种情况不需要讨论，它一定会被考虑在f[i][i+1]&&f[i+2][i+2]里面

• 这样子写状态转移方程式是不够优的，舍弃

  2. 观察整个区间，拿支荧光笔画一下，长度为3的区间，

  • 这道题目给人以区间dp的一种新的理解，不能过于拘泥在 枚举区间内中的分割点，还可以直接使用区间内某个特定的分割点，什么意思呢？
    • 只要左端点的颜色 == 右端点的颜色，合并左右区间的时候

• 可以直接转移左区间或者右区间，因为我们可以直接一刷子涂满整个区间

• 不需要任何花费就能向外拓展一个格子。

• 此时我们发现，我们可以把左右区间的颜色相等情况单独的分离出来，即

• f[head][tail]=min(f[head + 1][tail], f[head][tail - 1])

3.当左右区间的颜色不符合的时候，用你最拿手的状态转移方程式

• f[head][tail]=min(f [head][k] + f[k+1][tail], f[head][tail] );

• 到这里我们就能写出整体的状态转移方程式子

  if(a[head-1] == a[tail-1]){
  f[head][tail]=min(f[head + 1][tail],f[head][tail-1]);
  continue;
  }
  for(int k = head; k <= tail; k++){
  f[head][tail]=min(f[head][k] + f[k+1][tail],f[head][tail]);
  }

3.总结

• 回顾一下做题的步骤
  1. 确定这是区间dp

2. 画上数轴枚举1，2，3的情况，尝试写出状态转移方程式

3. 通常我们直接考虑分割点左右两个区间的关系和合并的情况，这道题目不一样的地方就是为大家敲了个警钟

4. 同学们学竞赛要灵活！！！我们可以通过把一个长度为1的区间和len-1的区间单独拉出来考虑的啊！！！

• 下次呢？下次说不定不是长度为1的区间，可能是不同位置的长度为2的区间，一定要长个心眼

• 代码是死的，人是活得，记住，不要太过于拘泥于模板，这道题目就是在告诉大家，可以完善模板，特殊的情况可以特殊对待啊

（其实我也是看别人的代码才会做的233333，各位大佬太巨了啊）