涂色PAINT

题意： 给定一个长度为的颜色序列，初始颜色序列无颜色每，次可以选择使得都变成一种颜色，问最少多少次可以使得整个区间变成给定的颜色序列。
数据范围：，还是baidu才知道的~。
题解：
由于数据范围很小且涉及到区间操作，所以考虑区间。 表示将涂成
状态转移：对：

• 当，涂时可以顺便把涂了，涂时可以顺便把涂了，故此时
• 当，此时没法一并涂颜色了，枚举，故此时
• 代码：*

#include<bits/stdc++.h>
using namespace std;

const int N = 55;
char s[N];
int f[N][N];
int main()
{
    scanf("%s", s + 1);
    int n = strlen(s + 1);
    memset(f, 0x3f, sizeof f);
    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(s[l] == s[r]) f[l][r] = min(f[l + 1][r], f[l][r - 1]);
            else for(int m = l; m + 1 <= r; m++) f[l][r] = min(f[l][r], f[l][m] + f[m + 1][r]);
        }

    printf("%d\n", f[1][n]);

    return 0;
}