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