[SCOI2007]压缩
题目
题目描述
给一个由小写字母组成的字符串，我们可以用一种简单的方法来压缩其中的重复信息。压缩后的字符串除了小写字母外还可以（但不必）包含大写字母R与M，其中M标记重复串的开始，R重复从上一个M（如果当前位置左边没有M，则从串的开始算起）开始的解压结果（称为缓冲串）。
bcdcdcdcd可以压缩为bMcdRR，下面是解压缩的过程：
已经解压的部分解压结果缓冲串
bbbbMb.bMcbccbMcdbcdcdbMcdRbcdcdcdcdbMcdRRbcdcdcdcdcdcdcdcd
输入格式
输入仅一行，包含待压缩字符串，仅包含小写字母，长度为n。
输出格式
输出仅一行，即压缩后字符串的最短长度。
输入输出样例
输入 #1
aaaaaaa
输出 #1
5
输入 #2
bcdcdcdcdxcdcdcdcd
输出 #2
12
说明/提示
在第一个例子中，解为aaaRa，在第二个例子中，解为bMcdRRxMcdRR。
【限制】
50%的数据满足：
1
≤
n
≤
20
1≤n≤20
1≤n≤20
100%的数据满足：
1
≤
n
≤
50
1≤n≤50
1≤n≤50
原题链接
题解
思路
首先我们应该考虑3种情况： 1.当某一段字符中有压缩， 并且不是在最开始压缩的， 那么我们就不能把此处压缩 2.当这一段字符没有任何地方被压缩时， 我们可以将其压缩， 并且压缩后要再加上头部的M与尾部的R 3.当这段字符有且仅有开头有压缩， 我们可以将其压缩， 并且只用加上末尾的R就行了
接下来考虑状态转移方程：
因为不能压缩所以无压缩时的方程， 普通时候， 随便两处合起来都是它， 所以就两段的最大值加起来。 dp[2][l][r] = min (dp[2][l][r], min (dp[x][l][k]) + min (dp[y][k + 1][r]))) (0≤x≤2 0≤y≤2 l≤k<r)
能够压缩， 但普通时只能是两段都没有压缩的进行合并， 压缩时要加两个字符 dp[1][l][r] = min (dp[1][l][r], dp[1][l][k] + dp[1][k + 1][r]) （l≤k<r）
能够压缩， 能够由压缩得到， 普通时只能由一个头压缩加一个没压缩 dp[0][l][r] = min (dp[1][l][(l + r) / 2] + 2, dp[0][l][(l + r) / 2] + 1) dp[0][l][r] = min (dp[0][l][r], dp[0][l][k] + dp[1][k + 1][r]) （l≤k<r)
运用算法
区
间
d
p
区间dp
区间dp
主体算法
h
a
s
h
hash
hash
用来判断是否可以压缩
代码
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std
;
#define MAXN 100
class hash {
private:
unsigned long long h
[MAXN
+ 5], b
[MAXN
+ 5];
public:
int initial
(char *c
){
int n
= strlen
(c
);
b
[0] = 1;
h
[0] = 0;
for (int i
= 1; i
<= n
; i
++){
h
[i
] = h
[i
- 1] * 1331 + c
[i
- 1];
b
[i
] = b
[i
- 1] * 1331;
}
return n
;
}
unsigned long long access
(int l
, int r
){
return h
[r
+ 1] - h
[l
] * b
[r
- l
+ 1];
}
};
hash s
;
int dp
[3][MAXN
+ 5][MAXN
+ 5];
char c
[MAXN
+ 5];
int main(){
int n
;
scanf
("%s", c
+ 1);
n
= s
.initial(c
+ 1);
for (int i
= 1; i
<= n
; i
++){
for (int j
= 1; j
<= n
- i
+ 1; j
++){
dp
[1][j
][j
+ i
- 1] = i
;
dp
[0][j
][j
+ i
- 1] = 0x7f7f7f7f;
dp
[2][j
][j
+ i
- 1] = i
;
if (i
% 2 == 0) {
if (s
.access(j
- 1, j
+ i
/ 2 - 2) == s
.access(j
+ i
/ 2 - 1, j
+ i
- 2)){
dp
[0][j
][j
+ i
- 1] = min
(dp
[1][j
][j
+ i
/ 2 - 1] + 2, dp
[0][j
][j
+ i
/ 2 - 1] + 1);
}
}
if (j
== 1){
dp
[0][j
][j
+ i
- 1] = min
(i
, dp
[0][j
][j
+ i
- 1]);
}
for (int k
= j
; k
< i
+ j
- 1; k
++){
dp
[1][j
][j
+ i
- 1] = min
(dp
[1][j
][j
+ i
- 1], dp
[1][j
][k
] + dp
[1][k
+ 1][j
+ i
- 1]);
dp
[0][j
][j
+ i
- 1] = min
(dp
[0][j
][j
+ i
- 1], dp
[0][j
][k
] + dp
[1][k
+ 1][j
+ i
- 1]);
dp
[2][j
][j
+ i
- 1] = min
(dp
[2][j
][j
+ i
- 1], min
(dp
[0][j
][k
], min
(dp
[1][j
][k
], dp
[2][j
][k
])) + min
(dp
[0][k
+ 1][i
+ j
- 1], min
(dp
[1][k
+ 1][i
+ j
- 1], dp
[2][k
+ 1][i
+ j
- 1])));
}
}
}
printf
("%d", min
(dp
[0][1][n
], min
(dp
[1][1][n
], dp
[2][1][n
])));
}
