题解 | [CQOI2007]涂色PAINT

//  #牛客春招刷题训练营# https://www.nowcoder.com/discuss/726480854079250432
//  又是看了题解才写出题目的一次，题解说染色问题优先想到dp
/*#include <iostream>
#include <string>
#include <vector>
#define pre(i, j, k) for (int i = j; i < k; i++)
using namespace std;

int main() {
  ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
  string s;
  cin >> s;
  char lc, rc;
  int ans = 0;
  size_t size = s.size();
  int l = 0, r = s.size() - 1;
  while(l < r){
    while(l + 1 < size && s[l] == s[l + 1]) l++;
    while(r - 1 > -1 && s[r] == s[r - 1]) r--;
    if (l >= r){
      ans++;
      break;
    }
    if (s[l] == s[r]){
      ans++;
      l++;
      r--;
    }
    else if (s[l] == s[r - 1] || s[l + 1] == s[r]){
      ans++;
      if (s[l] == s[r - 1]) r--;
      else l++;
    }
    else
  }
}
// 64 位输出请用 printf("%lld")*/
#include<iostream>
#include<algorithm>
#include<string>
#define pre(i,j,k) for(int i = j; i < k; i++)
using namespace std;
int dp[60][60];
int main(){
  ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
  string s;
  cin >> s;
  size_t size = s.size();
  pre(len, 1, 1 + size){
    pre(i, 0, size){
      int j = i + len - 1;
      if (j >= size) break;
      dp[i][j] = 0x3f3f3f3f;//--------初始化，不然后面不能min
      if (i == j) dp[i][j] = 1;//----------如果只有一个板子一个颜色那么就涂一次
      else if (s[i] == s[j]) dp[i][j] = min(dp[i][j - 1], dp[i + 1][j]);//---------如果两端相等，可以让两端共用一次涂色
      else {//----------否则枚举出最小
        pre(k, i, j){
          dp[i][j] = min(dp[i][k] + dp[k + 1][j], dp[i][j]);
        }
      }
    }
  }
  cout << dp[0][size - 1];
  return 0;
}