【每日一题】[SCOI2007]压缩
[SCOI2007]压缩
https://ac.nowcoder.com/acm/problem/20252
好久没写每日一题了，今天开始重拾算法QAQ
题目
题目描述：
给一个由小写字母组成的字符串，我们可以用一种简单的方法来压缩其中的重复信息。
压缩后的字符串除了小 写字母外还可以（但不必）包含大写字母R与M，其中M标记重复串的开始，R重复从上一个M（如果当前位置左边没 有M，则从串的开始算起）开始的解压结果（称为缓冲串）。
bcdcdcdcd可以压缩为bMcdRR，下面是解压缩的过程
另一个例子是abcabcdabcabcdxyxyz可以被压缩为abcRdRMxyRz。
输入描述：
输入仅一行，包含待压缩字符串，仅包含小写字母，长度为n。
输入仅一行，包含待压缩字符串，仅包含小写字母，长度为n。
输出描述：
输出仅一行，即压缩后字符串的最短长度。
输出仅一行，即压缩后字符串的最短长度。
解析
1）知识点
- 这道题考察的点就是区间dp，不过增加了一点难度。
2）看题目
- 题目告诉我们一段字符串可以压缩。那么问题就是怎么压缩了。
- 我们看题目可以发现，一段有重复字符串的区间才可以压缩。
- 看到这里我们就可以想到用到区间dp了。
3）算法分析
- 说到dp就不能忘了这句话：动态规划最重要的就是递推和dp数组的含义。
- 以前也有写过一道区间dp，我们再来说一下数组的含义是什么呢：
- 区间dp一般为二维数组，分别为区间左右端点，值为所需值。
- 但是这道题有一个地方不同，我们的选取区间一定是连续的区间，也就是说，我们区间中包含多个区间的时候我们要将他们分开。而分开的基础就是M字符的位置。
- 所以呢，我们在这个dp数组上面再加一个维度：区间内是否具有M。所以就有了：
int dp[MAX][MAX][2];//dp[左端点][右端点][区间内是否有M]=左到右的最小长度
- 得到了数组之后我们再来看递推：
- 递推有三点非常重要。
- 一是当有重复字符串我们要创造出一个M来：
- 二是当区间内没有M字符串，但是M在区间的前一个位置时（说明有一个前缀为可重复的），我们后面还有相同的字符串，我们就用R代替：
- 三是当区间内有M字符串的时候，我们就要分开来，分别压缩：
- 然后要注意2和3都要进行对M位置的判断就好了（就是用一个循环假设一切M可能在的位置）。
4）算法操作
- 根据上面的说法，我们已经知道了大概的一个操作。
- 首先我们知道了数组是什么样子的：
int dp[MAX][MAX][2];//dp[左端点][右端点][区间内是否有M]=左到右的最小长度
- 然后我们就是递推了：（首先要注意每一个区间的最小值都要初始化为区间长度）
- 我们2和3步骤的递推都要进行一个循环探测位置，所以我们可以放在一起进行：
for (int k = i; k <= j; k++) { dp[i][j][0] = min(dp[i][j][0], dp[i][k][0] + j - k); //当区间中没有M时，判断前面有没有连续相同字符串（判断i的前一位是不是M） int mn = min(dp[i][k][0], dp[i][k][1]) + min(dp[k + 1][j][0], dp[k + 1][j][1]) + 1; dp[i][j][1] = min(dp[i][j][1], mn); //当区间中有M时，M左右要分开（保证M含义），然后分别压缩，长度+1（加上M） } - 然后对1步骤进行特判，假如满足条件时我们就可以创造出M：
if (len % 2 == 0 && judge(i, j)) dp[i][j][0] = min(dp[i][j][0], dp[i][i + j >> 1][0] + 1); //特判一个区间左右对半正好是重复的情况，这样可以得到一个区间最起始的M
- 这里注意一下判断方法就好了（这个简单）：
bool judge(int l, int r) { int mid = (l + r >> 1) + 1; while (mid <= r) { if (s[l] != s[mid]) return false; l++; mid++; } return true; }
5）打代码
- 打代码啦~
- 根据我说的，先就输入字符串。
- 然后双层循环进行遍历，外层长度内层左端点（因为要从短到长，是dp的底层结构完整，所以循环不能设置为左右端点）
- 接下来就是按我说的进行递推就好啦。
- 最后输出中间有或没有M的最小值。
- 看我代码啦~
AC代码
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
#define IOS ios::sync_with_stdio(false);
const int MAX = 1e3 + 7;
int dp[MAX][MAX][2];//dp[左端点][右端点][区间内是否有M]=左到右的最小长度
string s;
bool judge(int l, int r);//判断s从l到r的偶数长字串是否左右相等
int main() {
IOS;
cin >> s;
int lens = s.length();//字符串s的长度
s = ' ' + s;
for (int len = 1; len <= lens; len++)//外层循环调节区间长度
for (int i = 1; i + len - 1 <= lens; i++) {//内层循环调节左端点位置
int j = i + len - 1;//计算出右端点位置
dp[i][j][0] = dp[i][j][1] = len;//最短初始化为区间长
for (int k = i; k <= j; k++) {
dp[i][j][0] = min(dp[i][j][0], dp[i][k][0] + j - k);
//当区间中没有M时，判断前面有没有连续相同字符串（判断i的前一位是不是M）
int mn = min(dp[i][k][0], dp[i][k][1]) + min(dp[k + 1][j][0], dp[k + 1][j][1]) + 1;
dp[i][j][1] = min(dp[i][j][1], mn);
//当区间中有M时，M左右要分开（保证M含义），然后分别压缩，长度+1（加上M）
}
if (len % 2 == 0 && judge(i, j)) dp[i][j][0] = min(dp[i][j][0], dp[i][i + j >> 1][0] + 1);
//特判一个区间左右对半正好是重复的情况，这样可以得到一个区间最起始的M
}
cout << min(dp[1][lens][0], dp[1][lens][1]) << endl;//输出长度较小的情况
return 0;
}
bool judge(int l, int r) {
int mid = (l + r >> 1) + 1;
while (mid <= r) {
if (s[l] != s[mid]) return false;
l++; mid++;
}
return true;
}每日一题 文章被收录于专栏
憨憨的专栏
查看15道真题和解析