[SCOI2003]字符串折叠
一道比较普通的 区间DP 题。
题意：定义了折叠操作，如 \(\texttt{ABCABC}\) 可折叠为 \(\texttt{2(ABC)}\)，也可以嵌套折叠。注意：字符串中两位数是算两个数位。问折叠操作后最小的字符串长度。
首先，题目意思很清楚，而且如果不算折叠就是输出字符串原长，折叠这个操作是一个区间一个区间来的，所以可以用区间DP来做。
定义状态：\(f_{i,j}\) 表示字符串 \(s[i,i+1,...,j]\) 折叠后的最小长度。
关于状态转移，分两种情况考虑：
- 这个区间不是折叠构成的，那么就按照套路枚举中间点正常转移即可。
- 这个区间是由折叠构成的，那么枚举这个折叠字符串的区间长度，判大字符串是否有这个折叠字符串构成即可。
代码
/*
I hope JLQ can bless me to AC the problem.
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 105;
int n, f[N][N];
string s;
int JLQ (int x) {
int cnt = 0;
while (x) ++cnt, x /= 10;
return cnt;
}
bool check (int l, int r, int k) {
if ((r - l + 1) % k != 0) return false;
int c = (r - l + 1) / k;
for (int i = 0; i < k; ++i) {
int t = l + i;
for (int j = 0; j < c; ++j)
if (s[t + k * j] != s[t]) return false;
}
return true;
}
int main() {
cin >> s;
n = s.size(); s = " " + s;
memset(f, 0x3f, sizeof(f));
for (int i = 1; i <= n; ++i)
f[i][i] = 1;
for (int len = 2; len <= n; ++len) {
for (int i = 1; i + len - 1 <= n; ++i) {
int j = i + len - 1;
f[i][j] = len;
for (int k = i; k < j; ++k)
f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j]);
for (int k = 1; i + k - 1 <= j; ++k)
if (check(i, j, k))
f[i][j] = min(f[i][j], JLQ((j - i + 1) / k) + 2 + f[i][i + k - 1]);
}
}
// cerr << "***" << f[6][11] << endl;
printf("%d\n", f[1][n]);
return 0;
}