Problem Specification Value
Time Limit 1 Sec
Memory Limit 128 MB
Submit 877
Solved 549

Description

给一个由小写字母组成的字符串, 我们可以用一种简单的方法来压缩其中的重复信息. 压缩后的字符串除了小写字母外还可以 (但不必) 包含大写字母 R 与 M, 其中 M 标记重复串的开始, R 重复从上一个 M (如果当前位置左边没有 M, 则从串的开始算起) 开始的解压结果 (称为缓冲串). bcdcdcdcd 可以压缩为 bMcdRR, 下面是解压缩的过程

无图片无真相

另一个例子是 abcabcdabcabcdxyxyz 可以被压缩为 abcRdRMxyRz.

Input

输入仅一行, 包含待压缩字符串, 仅包含小写字母, 长度为 n.

Output

输出仅一行, 即压缩后字符串的最短长度.

Sample Input

bcdcdcdcdxcdcdcdcd

Sample Output

12

HINT

在第一个例子中, 解为 aaaRa, 在第二个例子中, 解为 bMcdRRxMcdRR.

【限制】

100% 的数据满足: 1<=n<=50 100% 的数据满足: 1<=n<=50

Source

区间 DP, 选择一个区间被折半/不对折的成本, 每一次判断 O (n), 需要 O (n3) 次查询, 故复杂度为 O (n4).


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

using namespace std;
const int maxn = 100;
char str[maxn];
int dp_dat[maxn][maxn][2]; // Not using memorization techniques can be *COSTLY*!
bool dp_saved[maxn][maxn][2];

// Whether the string at [l, r] is foldable, symmetrically
bool foldable(int l, int r)
{
    int len = r - l + 1,
        mid = (l + r) >> 1,
        half_len = len >> 1;
    if (len & 1) // Odd length, determined to be incorrect
        return false;
    for (int i = 0; i < half_len; i++)
        if (str[l + i] != str[mid + 1 + i])
            return false;
    return true;
}

// Dynamic programming in the interval [l, r], and whether there would be
// 'M' characters inside this interval.
int dp(int l, int r, int has_m)
{
    int len = r - l + 1;
    if (len == 1) // Always of the size 1, undoubtedly
        return 1;
    // Memorized searching
    if (dp_saved[l][r][has_m])
        return dp_dat[l][r][has_m];
    dp_saved[l][r][has_m] = true;
    // The second half can be splittable
    if (has_m)
        for (int i = l; i < r; i++)
            len = min(len, dp(l, i, true) + dp(i + 1, r, true) + 1);
    // The second half not to be splitted
    for (int i = l; i < r; i++)
        len = min(len, dp(l, i, has_m) + (r - i));
    // If foldable, fold it and see what happens.
    if (foldable(l, r))
        len = min(len, dp(l, (l + r) >> 1, false) + 1); // +1 -> 'M'
    dp_dat[l][r][has_m] = len;
    return len;
}

int main(int argc, char** argv)
{
    scanf("%s", str + 1);
    int len = strlen(str + 1);
    int res = dp(1, len, true);
    printf("%d\n", res);
    return 0;
}
无