Problem Specification Value
Time Limit 10 Sec
Memory Limit 162 MB
Submit 1028
Solved 666

Description

折叠的定义如下: 1. 一个字符串可以看成它自身的折叠. 记作 S S 2. X (S) 是 X (X>1) 个 S 连接在一起的串的折叠. 记作 X (S) SSSS...... S (X 个 S). 3. 如果 A A ‘, BB’, 则 AB A ‘B’ 例如, 因为 3 (A)=AAA, 2 (B)=BB, 所以 3 (A) C2 (B) AAACBB, 而 2 (3 (A) C) 2 (B) AAACAAACBB 给一个字符串, 求它的最短折叠. 例如 AAAAAAAAAABABABCCD 的最短折叠为: 9 (A) 3 (AB) CCD.

Input

仅一行, 即字符串 S, 长度保证不超过 100.

Output

仅一行, 即最短的折叠长度.

Sample Input

NEERCYESYESYESNEERCYESYESYES

Sample Output

14

HINT

一个最短的折叠为: 2 (NEERC3 (YES))

Source

又是一道区间 DP 问题.

考虑每一个区间的折叠的最佳结果, 复杂度应该不超过 O (n^3).

记得记忆化搜索~


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

using namespace std;
const int maxn = 200;

char str[maxn];
bool dp_done[maxn][maxn];
int  dp_data[maxn][maxn];

// This function judges whether str[cl, cr] can be repeated in str[l, r] as a
// subset. Exempli gratis:
//     str = "ABCABCABCABC",
//     l = 3, r = 11 -> "ABCABCABC"
//     cl = 3, r = 5 -> "ABC",
// Then it should return true and vice versa.
bool judge_repeatable(int l, int r, int cl, int cr)
{
    // Should the string be indivisible, return false.
    if ((r - l + 1) % (cr - cl + 1) != 0)
        return false;
    // Check if this repetition is correct throughout all characters.
    for (int i = l; i <= r; i++)
        if (str[i] != str[(i - l) % (cr - cl + 1) + cl])
            return false;
    // Therefore this is correct.
    return true;
}

// This gets the digits of number x in decimal.
int get_digits(int x)
{
    int dig = 0;
    while (x > 0) {
        x /= 10;
        dig++;
    }
    return dig;
}

// The core dynamic programming function of this program.
int dp(int l, int r)
{
    // We assure this is sustaining.
    if (l == r)
        return 1;
    // Memorized searching.
    if (dp_done[l][r])
        return dp_data[l][r];
    // Prevent further, useless iterations.
    dp_done[l][r] = true;
    // deflated_min is the minimum length of the deflated string, which strictly
    // is smaller or equal to the length of this substring passed into this
    // function.
    int deflated_min = r - l + 1;
    // Scan for all substrings for potential deflation, as though this substring
    // is repeated throughout the following remainder of substrings.
    for (int i = l; i < r; i++) {
        // Split the string at this position.
        deflated_min = min(deflated_min, dp(l, i) + dp(i + 1, r));
        // If this string is repeatable, then attempt to repeat this string.
        if (judge_repeatable(i + 1, r, l, i))
            deflated_min = min(deflated_min, dp(l, i) + 2 + get_digits((r - i) / (i - l + 1) + 1));
    }
    // Save data for memorized searching.
    dp_data[l][r] = deflated_min;
    return deflated_min;
}

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