好久没写每日一题了,今天开始重拾算法QAQ


题目

题目描述:
给一个由小写字母组成的字符串,我们可以用一种简单的方法来压缩其中的重复信息。
压缩后的字符串除了小 写字母外还可以(但不必)包含大写字母R与M,其中M标记重复串的开始,R重复从上一个M(如果当前位置左边没 有M,则从串的开始算起)开始的解压结果(称为缓冲串)。 
bcdcdcdcd可以压缩为bMcdRR,下面是解压缩的过程
   
另一个例子是abcabcdabcabcdxyxyz可以被压缩为abcRdRMxyRz。

输入描述:
输入仅一行,包含待压缩字符串,仅包含小写字母,长度为n。

输出描述:
输出仅一行,即压缩后字符串的最短长度。


解析

1)知识点

  • 这道题考察的点就是区间dp,不过增加了一点难度。

2)看题目

  1. 题目告诉我们一段字符串可以压缩。那么问题就是怎么压缩了。
  2. 我们看题目可以发现,一段有重复字符串的区间才可以压缩
  3. 看到这里我们就可以想到用到区间dp了。

3)算法分析

  1. 说到dp就不能忘了这句话:动态规划最重要的就是递推和dp数组的含义
  2. 以前也有写过一道区间dp,我们再来说一下数组的含义是什么呢:
    1. 区间dp一般为二维数组,分别为区间左右端点,值为所需值。
    2. 但是这道题有一个地方不同,我们的选取区间一定是连续的区间,也就是说,我们区间中包含多个区间的时候我们要将他们分开。而分开的基础就是M字符的位
    3. 所以呢,我们在这个dp数组上面再加一个维度:区间内是否具有M。所以就有了:
      int dp[MAX][MAX][2];//dp[左端点][右端点][区间内是否有M]=左到右的最小长度
  3. 得到了数组之后我们再来看递推
  4. 递推有三点非常重要。
    1. 一是当有重复字符串我们要创造出一个M来:
    2. 二是当区间内没有M字符串,但是M在区间的前一个位置时(说明有一个前缀为可重复的),我们后面还有相同的字符串,我们就用R代替:
    3. 三是当区间内有M字符串的时候,我们就要分开来,分别压缩:
  5. 然后要注意2和3都要进行对M位置的判断就好了(就是用一个循环假设一切M可能在的位置)。

4)算法操作

  1. 根据上面的说法,我们已经知道了大概的一个操作。
  2. 首先我们知道了数组是什么样子的
    int dp[MAX][MAX][2];//dp[左端点][右端点][区间内是否有M]=左到右的最小长度
  3. 然后我们就是递推了:(首先要注意每一个区间的最小值都要初始化为区间长度
  4. 我们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)
    }
  5. 然后对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
  6. 这里注意一下判断方法就好了(这个简单):
    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)打代码

  1. 打代码啦~
  2. 根据我说的,先就输入字符串。
  3. 然后双层循环进行遍历,外层长度内层左端点(因为要从短到长,是dp的底层结构完整,所以循环不能设置为左右端点
  4. 接下来就是按我说的进行递推就好啦。
  5. 最后输出中间有或没有M的最小值。
  6. 看我代码啦~


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;
}