SCOI 2007 压缩 【动态规划】

和SCOI2003字符串一样，但又完全不一样

首先肯定是区间dp，然后考虑如何合并区间，两种情况：

1. 从中间分开，两边相同，也就是使用了压缩
2. 通过两个子区间合并起来

然后烦人的就来了，因为在压缩操作中，R会自动匹配成最近的M，那么也就是说当合并区间的时候，第一个区间的M有可能会影响第二个区间，所以我们要再加一维，表示这个区间里面有没有用到M，然后直接合并就ok了

然后一个很烦事情是，如何统计M，因为当统计xMaRR这种情况的时候，刚才的合并会搞两个M出来，也就是xMMaRR，两种做法：1. 再加一维，表示是否在当前串的开头有M，诶，就是玩儿，爷不怕麻烦 2. 当使用压缩操作时，只给贡献加1，也就是说不算M，当两个区间合并的第二种情况的时候，再把M加进去，因为这个时候是肯定会用到这个M了，即使有两个连续的R也不会算重，因为M在压缩操作里并没有计算贡献

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define gi get_int()
const int MAXN = 300, BASE = 998244353;
int get_int()
{
  int x = 0, y = 1;
  char ch = getchar(); 
  while (!isdigit(ch) && ch != ‘-‘)
    ch = getchar();
  if (ch == ‘-‘)
    y = -1, ch = getchar();
  while (isdigit(ch))
    x = x * 10 + ch - ‘0‘, ch = getchar();
  return x * y;
}

unsigned long long HASH[MAXN];
int dp[MAXN][MAXN][2];

unsigned long long qPow(int x, int y)
{
  unsigned long long ans = 1, b = x;
  while (y != 0) {
    if (y & 1)
      ans *= b;
    b *= b;
    y >>= 1;
  }
  return ans;
}

unsigned long long getHash(int pos, int len)
{
  return HASH[pos + len - 1] - (pos == 0 ? 0 : HASH[pos - 1] * qPow(BASE, len));
}

int main()
{
  std::string str;
  std::cin >> str;
  int n = str.size();
  for (int i = 0; i < n; i++)
    HASH[i] = (i == 0 ? 0 : HASH[i - 1] * BASE) + str[i];
  memset(dp, 0x3f, sizeof(dp));
  for (int i = 0; i < n; i++)
    for (int j = i; j < n; j++)
      dp[i][j][0] = (j - i) + 1;
  for (int size = 1; size <= n; size++) {
    for (int i = 0; i < n; i++) {
      int j = i + size - 1;
      int mid = (i + j) / 2;
      if (size % 2 == 0 && getHash(i, size / 2) == getHash(mid + 1, size / 2)) {
        dp[i][j][0] = std::min(dp[i][j][0], dp[i][mid][0] + 1);
      }
      for (int k = i; k < j; k++) {
        dp[i][j][0] = std::min(dp[i][j][0], dp[i][k][0] + j - k);
        dp[i][j][1] = std::min(dp[i][j][1], std::min(dp[i][k][0], dp[i][k][1]) + std::min(dp[k + 1][j][0], dp[k + 1][j][1]) + 1);
      }
    }
  }
  std::cout << std::min(dp[0][n - 1][1], dp[0][n - 1][0]);
  
  return 0;
}

SCOI 2007 压缩 【动态规划】

原文：https://www.cnblogs.com/enisP/p/14808193.html