字符串折叠&压缩(区间DP)

字符串折叠

题目描述

折叠的定义如下:

  1. 一个字符串可以看成它自身的折叠。记作S = S
  2. X(S)是X(X>1)个S连接在一起的串的折叠。记作X(S) = SSSS…S(X个S)。
  3. 如果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;
}
上一篇:JS特殊符号


下一篇:转载:Cellebrite发布新版手机取证软件,增强调查能力