题解 P4170 【[CQOI2007]涂色】

· · 题解

讲一下前面的题解没有细讲的一个点。

用dp[i][j]表示i\ to\ j段的最少涂色次数

dp[i][i] = 1

当s[i]=s[j]，即首尾颜色相同时，作如下思考：

对于任意的x\ to\ y段，涂的底色不同时，最少涂色次数相差不超过1（假设用A作底色涂色次数最少，为m，那用B作底色时最少涂色次数必定不超过m+1，即在以A为底色的底下再涂一层B）。

对于当前我们讨论的i\ to\ j段，假设s[i]=s[j]=C，我们先看i+1\ to\ j-1段（假如有的话），令t=dp[i+1][j-1]，则假设以C为底色，i+1\ to\ j-1段最少涂色次数为t或t+1。

假设为t，即以C为底色i+1\ to\ j-1段可以达到最少次数，那么只要在第一次涂的时候涂到i即可得i\ to\ j-1段，即dp[i][j-1]\leq t=dp[i+1][j-1]，

又dp[i][j-1]\geq dp[i+1][j-1]（不可能多了一段涂色次数反而变少）

即可得dp[i][j-1]=dp[i+1][j-1]，且此时是以C为底色取得的最小值，同理可得dp[i][j]=dp[i][j-1]

假设为t+1，即C不是i+1\ to\ j-1段涂底色的最优选，则dp[i][j-1]=t+1且C为底色

可以归纳得到，对于区间x\ to\ y，总有一种方法可以以s[x]为底色且取得最小值，右边同理。

回到i\ to\ j段，易知dp[i][j]=dp[i][j-1]，只要i\ to\ j-1段以C为底色，往右多涂一段。右边同理。事实上，dp[i][j-1]=dp[i+1][j]，所以这 里其实不需要取min。 后面的思路就是一样的了，s[i]\neq s[j]时，把区间分成两段，枚举断点。


#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;
int main()
{
    int n, i, j, k, l, t, dp[60][60];
    char s[60];
    scanf("%s", s);
    n = strlen(s);
    for (i = 0; i < n; ++i)
    {
        for (j = 0; j < 26; ++j)
        {
            dp[i][i] = 1;
        }
    }
    for (l = 1; l < n; ++l)
    {
        for (i = 0; i + l < n; ++i)
        {
            if (s[i] == s[i + l])
            {
                dp[i][i + l] = dp[i][i + l - 1];
            }
            else
            {
                dp[i][i + l] = dp[i][i] + dp[i + 1][i + l];
                for (k = i + 1; k < i + l; ++k)
                {
                    dp[i][i + l] = min(dp[i][i + l], dp[i][k] + dp[k + 1][i + l]);
                }
            }
        }
    }
    printf("%d", dp[0][n - 1]);
    return 0;
}