本题是 P4302 [SCOI2003]字符串折叠 的强化版。
不难看出这是一个区间 dp，令 dp[i][j] 表示区间 $[l,r]$ 的最小长度。考虑两种操作：
合并两个小区间后变为一个大区间
将某个区间进行折叠
第一个操作，显然就是区间 dp 的套路方法，即：
1
2
| for (int k = l;k < r;++k)
dp[l][r] = min (dp[l][r],dp[l][k] + dp[k + 1][r]);
|
第二个操作，对于一个 $[l,r]$ 的字符串，若要被折叠成长度为 $k$ 的字符串，在执行的时候需要满足 $1 \le k \le r - l + 1$ 且 $k \mid r - l +1$ 且 $\forall i \in [l,r - k], str[i] = str[i + k]$。符合要求，则可以转移 dp[l][r] = min (dp[l][r],2 + calc ((r - l + 1) / k) + dp[l][l + k - 1])。其中的 $2$ 即两个括号的长度，calc (x) 计算的是重复次数表示成字符串时的位数，dp[l][l + k - 1] 即循环节。
在得到最小长度后，由于需要输出合法的方案，所以我们在此基础上还要记录一些断点的信息，从而进行搜索。用两个数组分别记录第一和第二种的操作的断点，第一种操作记录断点的编号，第二种操作记录循环节的长度。由于一个区间的处理只进行一种操作，所以在标记时要把另外一种操作的断点设为 $0$。
在递归时，对于一个区间若两种断点均不存在，则直接输出这段区间；若是第一种操作的断点 $k$，则分别递归区间 $[l,k]$ 和 $[k + 1,r]$；若是第二种，则先输出左括号和重复的次数，递归循环节的区间，在输出右括号即可。
完整代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
| #include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define init(x,y) memset (x,y,sizeof (x))
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
using namespace std;
const int MAX = 105;
const int MOD = 1e9 + 7;
char str[MAX];
int n,dp[MAX][MAX],cut[MAX][MAX],fold[MAX][MAX];
void check (int l,int r,int k);
int calc (int num);
void dfs (int l,int r);
int main ()
{
while (scanf ("%s",str + 1) != EOF)
{
n = strlen (str + 1);
init (dp,INF);init (cut,0);init (fold,0);
for (int i = 1;i <= n;++i) dp[1][i] = i,dp[i][i] = 1;
for (int i = 1;i <= n;++i)
{
for (int l = 1;l <= n;++l)
{
int r = i + l;
if (r > n) break;
for (int k = 1;k <= (r - l + 1) / 2;++k) check (l,r,k);
for (int k = l;k < r;++k)
{
if (dp[l][k] + dp[k + 1][r] < dp[l][r])
{
dp[l][r] = dp[l][k] + dp[k + 1][r];
cut[l][r] = k;
fold[l][r] = 0;
}
}
}
}
dfs (1,n);
puts ("");
}
return 0;
}
void check (int l,int r,int k)
{
if ((r - l + 1) % k) return ;
for (int i = l;i <= r - k;++i)
if (str[i] != str[i + k]) return ;
int s = 2 + calc ((r - l + 1) / k) + dp[l][l + k - 1];
if (s < dp[l][r])
{
dp[l][r] = s;
cut[l][r] = 0;
fold[l][r] = k;
}
}
int calc (int num)
{
int cnt = 0;
while (num) num /= 10,++cnt;
return cnt;
}
void dfs (int l,int r)
{
if (!cut[l][r] && !fold[l][r]) for (int i = l;i <= r;++i) printf ("%c",str[i]);
else if (cut[l][r]) dfs (l,cut[l][r]),dfs (cut[l][r] + 1,r);
else
{
printf ("%d(",(r - l + 1) / fold[l][r]);
dfs (l,l + fold[l][r] - 1);
printf (")");
}
}
|
