题目描述
折叠的定义如下：
- 一个字符串可以看成它自身的折叠。记作S = S
- X(S)是X(X>1)个S连接在一起的串的折叠。记作X(S) = SSSS…S(X个S)。
- 如果A = A’, B = B’，则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。
输入格式
仅一行，即字符串S，长度保证不超过100。
输出格式
仅一行，即最短的折叠长度
emmmmm，首先题意上说明折叠后的长度是加上数字的长度和括号的， 设f[l][r]表示将区间[l, r]折叠后的最小长度， 显然初值是r - l + 1;然后我们去暴力枚举该区间可以有哪两个区间去合并， 然后就该考虑到它自身折叠的问题了， 可以暴力枚举它每一段的长度， 然后判断是否可以折叠， 设此时枚举长度为k且可以合并， 那么显然$f[l][r] = min(f[l][r], f[l][l + k - 1] + 2 + a[len / k]);$, 2为括号的长度， a数组表示数字的长度， 即1长度为1 ， 10长度为10等， 最后直接输出f[1][n]即可， 思路应该很清晰， 这道题还是比较水的（吧。。。）
#include <bits/stdc++.h> using namespace std; typedef long long ll;
const int INF = 0x3f3f3f3f;
const int MAXN = 5e5 + 100;
const int MAXM = 1e3 + 10;
const double eps = 1e-5; template < typename T > inline void read(T &x) {
x = 0; T ff = 1, ch = getchar();
while(!isdigit(ch)) {
if(ch == '-') ff = -1;
ch = getchar();
}
while(isdigit(ch)) {
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
x *= ff;
} template < typename T > inline void write(T x) {
if(x == 0) {
putchar('0');
return ;
}
if(x < 0) putchar('-'), x = -x;
static T tot = 0, ch[30];
while(x) {
ch[++tot] = x % 10 + '0';
x /= 10;
}
while(tot) putchar(ch[tot--]);
} int n, a[110], f[110][110];
char ch[110]; inline bool check(int l, int r, int len) {
for (int i = l; i <= r - len; ++i) {
if(ch[i] != ch[i + len]) return false;
}
return true;
} int main() {
scanf("%s", ch + 1);
n = strlen(ch + 1);
for (int i = 1; i <= 9; ++i) a[i] = 1;
for (int i = 10; i <= 99; ++i) a[i] = 2;
a[100] = 3;
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 l = 1; l <= n - len + 1; ++l) {
int r = l + len - 1;
f[l][r] = len;
for (int i = l; i < r; ++i) f[l][r] = min(f[l][r], f[l][i] + f[i + 1][r]);
for (int k = 1; k < len; ++k) {
if (len % k != 0) continue;
if (check(l, r, k)) f[l][r] = min(f[l][r], f[l][l + k - 1] + 2 + a[len / k]);
}
}
}
write(f[1][n]);
return 0;
}
题目描述
给一个由小写字母组成的字符串，我们可以用一种简单的方法来压缩其中的重复信息。压缩后的字符串除了小写字母外还可以（但不必）包含大写字母R与M，其中M标记重复串的开始，R重复从上一个M（如果当前位置左边没有M，则从串的开始算起）开始的解压结果（称为缓冲串）。
bcdcdcdcd可以压缩为bMcdRR，下面是解压缩的过程：
| 已经解压的部分 | 解压结果 | 缓冲串 |
|---|---|---|
| b | b | b |
| bM | b | . |
| bMc | bc | c |
| bMcd | bcd | cd |
| bMcdR | bcdcd | cdcd |
| bMcdRR | bcdcdcdcd | cdcdcdcd |
输入格式
输入仅一行，包含待压缩字符串，仅包含小写字母，长度为n。
输出格式
输出仅一行，即压缩后字符串的最短长度。
刚看到这道题， ？？双倍经验？？也就瞎写一波， 状态方法都是一样的， f[l][r]表示将区间[l, r]折叠的最短长度，当l等于1的时候特判第一个M就不需要了， 应该没问题， 嗯呢， 提交， 60， 好惨。。。可以用一组数据hack这个做法： aaaaaaaaaa， 最好的情况显然是5（aaRaR）， 但这个程序跑出来确实是6， 是因为R复制的是在它之前的第一个M， 所以R也会复制到R， 这样你就无法判断了， 所以R对应的M在哪就是一个需要解决的问题。 我们不妨开一个三维的数组， f[l][r][0]表示折叠[l ,r]且之间没有M的最短长度， 默认l - 1是M， f[l][r]][1]就表示之间有M， 对于每个M出现的位置， 我们也可以暴力去判断出现在哪里是最优的情况， 这样时间复杂度为$O(n^3)$， 输出$\min(f[1][n][0], f[1][n][1])$即可。
#include <bits/stdc++.h> using namespace std; typedef long long ll;
const int INF = 0x3f3f3f3f;
const int MAXN = 5e5 + 100;
const int MAXM = 1e3 + 10;
const double eps = 1e-5; template < typename T > inline void read(T &x) {
x = 0; T ff = 1, ch = getchar();
while (!isdigit(ch)) {
if(ch == '-') ff = -1;
ch = getchar();
}
while (isdigit(ch)) {
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
x *= ff;
} template < typename T > inline void write(T x) {
if (x == 0) {
putchar('0');
return ;
}
if (x < 0) putchar('-'), x = -x;
static T tot = 0, ch[30];
while (x) {
ch[++tot] = x % 10 + '0';
x /= 10;
}
while (tot) putchar(ch[tot--]);
} int n, a[110], f[60][60][2];
char ch[60]; inline bool check(int l, int r) {
int len = r - l + 1;
if (len & 1) return false;
int mid = len >> 1;
for (int i = l; i <= r - mid; ++i) {
if(ch[i] != ch[i + mid]) return false;
}
return true;
} int main() {
scanf("%s", ch + 1);
n = strlen(ch + 1);
memset(f, 0x3f, sizeof(f));
for (int i = 1; i <= n; ++i) {
f[i][i][0] = f[i][i][1] = 1;
}
for (int len = 2; len <= n; ++len) {
for (int l = 1; l <= n - len + 1; ++l) {
int r = l + len - 1;
f[l][r][0] = f[l][r][1] = len;
for (int i = l; i < r; ++i) f[l][r][1] = min(f[l][r][1], min(f[l][i][1], f[l][i][0]) + min(f[i + 1][r][1], f[i + 1][r][0]) + 1);
for (int i = l; i < r; ++i) f[l][r][0] = min(f[l][r][0], f[l][i][0] + r - i);
if (check(l, r)) f[l][r][0] = min(f[l][r][0], f[l][(l + r) >> 1][0] + 1);
}
}
write(min(f[1][n][0], f[1][n][1]));
return 0;
}