题解 | #[CQOI2007]涂色PAINT#

题解

定义dp[i][j]是区间str[i~j]上的最少涂色次数。
区间dp的核心思想是由一个个小区间合并成大区间， 所在在dp时应该从长度最短的区间考虑，就是长度为1的区间。

1.长度为1的区间

涂色次数为1

2.长度为2的区间

它可以由两个长度为1的区间合并，这个题的特殊地方在于一次可以涂一个连续区间。所以：
如果str[i]=str[j]，那这个长度为2的区间[i~j]只需要涂一次。
如果不同，就是两个区间次数相加了（2次）

3.长度为len的区间

仿照区间长度为2的时候，可以枚举区间中的某个分割点来进行分割，并且题目要求可以一次涂一整个区间，所以：

• str[i]==str[j]: dp[i][j] = min(dp[i][j-1], dp[i+1][j])，可以认为涂[i+1,j]的时候顺便涂上了str[i]，比如"...CBC..."，判断"CBC"区间的次数时，可以认为涂"BC"时顺便涂上了"C"
• str[i]!=str[j]: 枚举区间[i,j]内断点k，有dp[i][j] = min(dp[i][j], dp[i][k]+dp[k+1][j])

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 55;
int n;
char str[N];
int f[N][N];
int main() {

    scanf("%s", str+1);
    n = strlen(str+1);
    memset(f, 0x3f, sizeof(f));
    // 长度=1 的字符串需要1次涂色
    for(int i = 1; i <= n; i++) f[i][i] = 1;  
    for(int len = 2; len <= n; len++) {
        for(int l = 1; l+len-1 <= n; l++) {
            int r = l + len - 1;
            if(str[l]==str[r]){
                f[l][r] = min(f[l+1][r], f[l][r-1]);
            }else {
                for(int k = l; k < r; k++) {
                    f[l][r] = min(f[l][r], f[l][k]+f[k+1][r]);
                }
            }
        }
    }
    printf("%d\n", f[1][n]);
    return 0;
}
// 64 位输出请用 printf("%lld")