洛谷 P4170 CQOI2007 涂色

url: https://www.luogu.com.cn/problem/P4170

tag:
字符串，动态规划，枚举，区间DP

思路：
使用 f[i][j] 表示从i到j这个区间中如果要涂到规定的情况，最少需要的涂色次数。因为有区间，所以可以使用区间DP，对于每一各区间i到j来说如果第i个字符和第j个字符相同，则 f[i][j] 可以从 f[i][j - 1] 更新过来。如果不相同，则可以枚举这个区间中的每一个位置，将这个区间变为两个区间分别进行，由两个区间进行更新。初始状态，每个长度为1的区间，要达到规定的情况只需要涂一次就行。最后输出 f[0][n - 1] 即可。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 60;
int f[N][N];
int main()
{
    char s[60];
    cin >> s;
    int n = strlen(s);
    for (int i = 0; i < n; i ++) f[i][i] = 1;
    for (int l = 1; l < n; l ++)
    {
        for (int i = 0; i + l < n;  i++)
        {
            if (s[i] == s[i + l]) f[i][i + l] = f[i][i + l - 1];
            else
            {
                f[i][i + l] = f[i][i] + f[i + 1][i + l];
                for (int k = i + 1; k < i + l; k ++)
                    f[i][i + l] = min(f[i][i + l], f[i][k] + f[k + 1][i + l]);
            }
        }
    }
    cout << f[0][n - 1] << endl;
    return 0;
}