Description

假设你有一条长度为 \(5\) 的木版, 初始时没有涂过任何颜色. 你希望把它的 \(5\) 个单位长度分别涂上红、绿、蓝、绿、红色, 用一个长度为 5 的字符串表示这个目标:RGBGR. 每次你可以把一段连续的木版涂成一个给定的颜色, 后涂的颜色覆盖先涂的颜色. 例如 第一次把木版涂成 RRRRR, 第二次涂成 RGGGR, 第三次涂成 RGBGR, 达到目标. 用尽量少的涂色次数达到目标.

Input

输入仅一行, 包含一个长度为 \(n\) 的字符串, 即涂色目标. 字符串中的每个字符都是一个大写字母, 不同的字母代表不同颜色, 相同的字母代表相同颜色.

Output

仅一行, 包含一个数, 即最少的涂色次数.

Sample Input

RGBGR

Sample Output

3

Data Range

40% 的数据满足:\(1 \leq n \leq 10\)

100% 的数据满足:\(1 \leq n \leq 50\)

Explanation

就是一道区间 DP, 考虑每一段区间最少需要涂几次. 然后 DP 方程比较简单, 可以很快搞出来 (具体请看代码), 没必要在这里再说一遍了. 但是这样这道题看起来似乎就是一个 \(O(n^3)\) 的数据减弱版题目, 放在这里用 NP 复杂度吓唬人~

写代码的时候注意不要搞乱 (我把 \(len\) 和 \(l\) 搞混了)

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>

#define minimize(__x,__y) __x=min(__x,__y)
using namespace std;
typedef long long lli;
const int maxn = 60;
const int infinit = 0x003f3f3f;

int n, colour[maxn];
int dp[maxn][maxn];
char str[maxn];

int main(int argc, char** argv)
{
    scanf("%s", str + 1);
    n = strlen(str + 1);
    for (int i = 1; i <= n; i++)
        colour[i] = (int)str[i] - 'A' + 1;
    // Done reading data, cleaning DP array.
    for (int i = 0; i <= n + 1; i++)
        for (int j = 0; j <= n + 1; j++)
            dp[i][j] = infinit;
    // Setting initial states
    for (int i = 1; i <= n; i++)
        dp[i][i] = 1;
    // Running main DP procedure.
    for (int len = 2; len <= n; len++)
        for (int l = 1; l + len - 1 <= n; l++) {
            int r = l + len - 1;
            if (colour[l] == colour[r]) {
                // Same colour, choosing to choose any of it.
                if (len == 2) {
                    dp[l][r] = 1;
                } else {
                    minimize(dp[l][r], dp[l + 1][r]);
                    minimize(dp[l][r], dp[l][r - 1]);
                    minimize(dp[l][r], dp[l + 1][r - 1] + 1); // Recolouring block
                }
            } else {
                // Different colour, will split into two parts
                for (int mid = l; mid <= r - 1; mid++)
                    minimize(dp[l][r], dp[l][mid] + dp[mid + 1][r]);
            }
            // printf("dp(%d, %d) = %d\n", l, r, dp[l][r]);
        }
    int res = dp[1][n];
    printf("%d\n", res);
    return 0;
}