好久没写每日一题了,今天开始重拾算法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; }