洛谷 P4170 [CQOI2007] 涂色

// ✗ P4170 的第一版：**没有那个特判**，老老实实按区间划分。
//
//     f[l][r] = min over k of ( f[l][k] + f[k+1][r] )
//
// 这是从[石子合并](/sol/p1775/)那儿原样搬过来的手感 —— 但它漏掉了这道题的全部门道：
// **一刷可以跨过中间那些「后来会被盖掉」的格子**，所以两端同色时不该各算一次。
//
// ★ 方向能先说死：它只是**少了一种更省的拼法** ⇒ 答案**恒 ≥ 正解**。
//   ★ 官方那两组样例**都挡住了它**（AAAAA 打 5、RGBGR 打 5）——
//     因为它其实退化成了「一格一刷」：答案恒等于长度 n。页面上把这条也钉成了断言。

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

int main() {
    char buf[64];
    if (scanf("%63s", buf) != 1) return 0;
    string s = buf;
    int n = (int)s.size();
    vector<vector<int>> f(n + 2, vector<int>(n + 2, 0));
    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;
            int best = INT_MAX;
            for (int k = l; k < r; k++) best = min(best, f[l][k] + f[k + 1][r]);
            f[l][r] = best;                                    // ✗ 没有「两端同色」那一条
        }
    printf("%d\n", f[1][n]);
    return 0;
}

// P4170 [CQOI2007] 涂色 —— ★ 这一版就能 AC。
//
// f[l][r] = 把 [l, r] 这一段涂成目标的样子，最少要涂几次。
//
// ★★ 关键的一步：**两端颜色相同时，可以省下一次。**
//
//       s[l] == s[r]  ⇒  f[l][r] = min( f[l+1][r], f[l][r-1] )
//       否则          ⇒  f[l][r] = min over k of ( f[l][k] + f[k+1][r] )
//
//   为什么第一行成立：`s[l] == s[r]` 时，总存在一个最优方案，
//   让这两格**在同一次涂色里被盖住**（把盖住 l 的那一刷向右延到 r 不会变差 ——
//   后面涂的会覆盖先涂的，多刷到的地方都会被后来的盖掉）。
//   ⇒ 于是「这一刷」既服务了 l 也服务了 r，代价只算一次，
//     剩下的就是把 l（或 r）当成已经免费搭上的那一格。
//
// ⚠ 注意不能写成 `f[l+1][r-1] + 1`（见 p4170Inner.cpp）：那等于**强行规定**
//   这一刷只从 l 刷到 r 一整段、里面的事全部另算，会白花次数。
//
// 规模：`n ≤ 50` ⇒ 转移不到 2 万次，随便跑。

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

int main() {
    char buf[64];
    if (scanf("%63s", buf) != 1) return 0;
    string s = buf;
    int n = (int)s.size();
    vector<vector<int>> f(n + 2, vector<int>(n + 2, 0));
    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 - 1] == s[r - 1]) {
                f[l][r] = min(f[l + 1][r], f[l][r - 1]);       // ★ 两端同色，省一次
            } else {
                int best = INT_MAX;
                for (int k = l; k < r; k++) best = min(best, f[l][k] + f[k + 1][r]);
                f[l][r] = best;
            }
        }
    printf("%d\n", f[1][n]);
    return 0;
}

// ✗ P4170 的第二版：特判写成了 `f[l+1][r-1] + 1`。
//
// 「两端同色，那就先把 [l, r] 整段刷成这个颜色，再去解决中间」—— 听着很顺，
// 而且它**是一个合法的方案**，所以答案恒 ≥ 正解。
//
// ⚠ 它错在**把那一刷的范围钉死了**。正确的写法 `min(f[l+1][r], f[l][r-1])` 说的是：
//   那一刷只要**盖住 l 和 r**就行，中间刷到哪儿、刷了几段，都由子问题自己安排。
//
// ★ 最小的反例只要三个字符：`AAA` —— 正解 1（一刷刷完），而这一版算成 **2**。
//   （`f[2][2] + 1 = 2`：它非要「先刷整段、再单独处理中间那一格」。）
//   ⇒ 官方两组样例都挡住了它（AAAAA 打 3、RGBGR 打 3）。

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

int main() {
    char buf[64];
    if (scanf("%63s", buf) != 1) return 0;
    string s = buf;
    int n = (int)s.size();
    vector<vector<int>> f(n + 2, vector<int>(n + 2, 0));
    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;
            int best = INT_MAX;
            for (int k = l; k < r; k++) best = min(best, f[l][k] + f[k + 1][r]);
            if (s[l - 1] == s[r - 1]) best = min(best, f[l + 1][r - 1] + 1);   // ✗ 钉死了那一刷
            f[l][r] = best;
        }
    printf("%d\n", f[1][n]);
    return 0;
}