“双向”区间DP
一道很明显的区间DP,f[l,r]表示l~r折叠成的最小长度。
转移1:拆成两部分
f[l,r] = min{f[l,k] + f[k+1,r]} 的转移大家都会,就不用多说了。
转移2:循环生成
接下来如果按照一般思路,考虑l~r有哪个子串循环生成,会稍微有点麻烦。
其实动态规划的实现可以有两个方向:
- 考虑f[l,r]如何得到
- 考虑f[l,r]可以转移到哪些新的状态
甚至可以把两个方向结合起来——只要按照合理的阶段顺序把所有状态都计算一遍就行了。
所以我们可以改成不断重复f[l,r],尝试用它更新更长的f[l,ed],其中ed=r+len,r+2*len,…
详见代码注释。
打印方案
记录转移路径,递归输出即可。
时间复杂度
O(n^3)
C++代码
#include<bits/stdc++.h>
using namespace std;
int f[105][105], p[105][105], n;
char a[105];
bool equals(int r, int ed, int len) { // r,ed往前len个字符是否相同
for (int i = 0; i < len; i++)
if (a[r - i] != a[ed - i]) return false;
return true;
}
void print(int l, int r) {
if (!p[l][r]) {
for (int i = l; i <= r; i++) putchar(a[i]);
return;
}
if (p[l][r] > 0) {
print(l, p[l][r]);
print(p[l][r] + 1, r);
} else {
int len = -p[l][r];
printf("%d(", (r - l + 1) / len);
print(l, l + len - 1);
putchar(')');
}
}
int main() {
scanf("%s", a + 1);
n = strlen(a + 1);
memset(f, 0x3f, sizeof(f));
for (int len = 1; len <= n; len++)
for (int l = 1; l <= n - len + 1; l++) {
int r = l + len - 1;
// [l,r]拆分成两段
if (len == 1) f[l][r] = 1;
else for (int k = l; k < r; k++)
if (f[l][k] + f[k + 1][r] < f[l][r]) {
f[l][r] = f[l][k] + f[k + 1][r];
p[l][r] = k;
}
// [l,r]]重复cnt次生成更长的字符串[l,ed]
for (int ed = r + len, cnt = 2; ed <= n && equals(r, ed, len); ed += len, cnt++)
if (f[l][r] + 2 + std::to_string(cnt).length() < f[l][ed]) {
f[l][ed] = f[l][r] + 2 + std::to_string(cnt).length();
p[l][ed] = -len; // 负数表示由若干个长度为len的子串循环构成
}
}
print(1, n);
}
进阶指南的题比较难,但是感觉囊括的题型跟全面并且题目也很经典。👍
看了一圈,还是博主的方法巧妙
再简单我也想不到(哭)
tql
👍👍👍👍
大佬,请问
f[l][r] + 2 + std::to_string(cnt).length()
,为啥要这样做呢…感觉挺突然的f[l][r]代表循环节的长度,2是左右括号,再加上循环节的数量的数字表示长度就是新循环生成的的串的折叠表示长度。
soga,好直接暴力啊哈哈
转移一应该是取min吧,代码里好像也是
嗯对
orz