Folding
题面
折叠由大写字母组成的长度为 \(n\)(\(1\leqslant n\leqslant100\))的一个字符串,使得其成为一个尽量短的字符串,例如 AAAAAA
变成 6(A)
。
这个折叠是可以嵌套的,例如 NEEEEERYESYESYESNEEEEERYESYESYES
会变成 2(N5(E)R3(YES))
。
多解时可以输出任意解。
题解
首先,数据范围很小,可能是区间dp,又因为这玩意贪心肯定不对,而且我看题解了,就是区间dp
考虑怎么区间dp,设 \(f(l,r)\) 表示 \([l,r]\) 区间最短字符串长度,有两种转移方式
- 不折叠,枚举分界点,\(f(l,r) = f(l,k) + f(k + 1, r)\)
- 折叠,枚举循环子串长度 \(len\),\(f(l,r) = 2 + calc((r - l + 1) / len) + len\)
calc表示计算 x 的位数,2表示两个括号,len表示枚举的循环子串的长度
时间复杂度 \(O(n^4)\)