题解 | [CQOI2007]涂色PAINT

水题，跑一遍 O(n^3) 的区间 dp 即可，转移是显然（？）的。

#include<bits/stdc++.h>
using i64 = long long;

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    std::string s;
    std::cin >> s;
    int n = s.size();

    std::vector dp(n, std::vector<int>(n, n));
    for (int i = 0; i < n; i++) {
        dp[i][i] = 1;
    }

    for (int l = 2; l <= n; l++) {
        for (int i = 0; i + l - 1 < n; i++) {
            dp[i][i + l - 1] = std::min(dp[i][i + l - 1], dp[i + 1][i + l - 1] + !(s[i] == s[i + 1] || s[i] == s[i + l - 1]));
            dp[i][i + l - 1] = std::min(dp[i][i + l - 1], dp[i][i + l - 2] + !(s[i + l - 1] == s[i + l - 2] || s[i + l - 1] == s[i]));

            for (int j = 0; j < i + l - 1; j++) {
                dp[i][i + l - 1] = std::min(dp[i][i + l - 1], dp[i][j] + dp[j + 1][i + l - 1]);
            }
        }
    }

    std::cout << dp[0][n - 1];

    return 0;
}

https://www.nowcoder.com/discuss/727521113110073344