P4302 [SCOI2003]字符串折叠 题解

[SCOI2003]字符串折叠

一道比较普通的 区间DP 题。

题意：定义了折叠操作，如 $\texttt{ABCABC}$ 可折叠为 $\texttt{2(ABC)}$，也可以嵌套折叠。注意：字符串中两位数是算两个数位。问折叠操作后最小的字符串长度。

首先，题目意思很清楚，而且如果不算折叠就是输出字符串原长，折叠这个操作是一个区间一个区间来的，所以可以用区间DP来做。

定义状态：$f_{i,j}$ 表示字符串 $s[i,i+1,...,j]$ 折叠后的最小长度。

关于状态转移，分两种情况考虑：

1. 这个区间不是折叠构成的，那么就按照套路枚举中间点正常转移即可。
2. 这个区间是由折叠构成的，那么枚举这个折叠字符串的区间长度，判大字符串是否有这个折叠字符串构成即可。

代码

/*
I hope JLQ can bless me to AC the problem.
*/
#include <bits/stdc++.h>

using namespace std;

const int N = 105;

int n, f[N][N];
string s;

int JLQ (int x) {
  int cnt = 0;
  while (x) ++cnt, x /= 10;
  return cnt;
}

bool check (int l, int r, int k) {
  if ((r - l + 1) % k != 0) return false;
  int c = (r - l + 1) / k;
  for (int i = 0; i < k; ++i) {
    int t = l + i;
    for (int j = 0; j < c; ++j)
      if (s[t + k * j] != s[t]) return false;
  }
  return true;
}

int main() {
  cin >> s;
  n = s.size(); s = " " + s;
  memset(f, 0x3f, sizeof(f));
  for (int i = 1; i <= n; ++i)
    f[i][i] = 1;
  for (int len = 2; len <= n; ++len) {
    for (int i = 1; i + len - 1 <= n; ++i) {
      int j = i + len - 1;
      f[i][j] = len;
      for (int k = i; k < j; ++k)
        f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j]);
      for (int k = 1; i + k - 1 <= j; ++k)
        if (check(i, j, k))
          f[i][j] = min(f[i][j], JLQ((j - i + 1) / k) + 2 + f[i][i + k - 1]);
    }
  }
//  cerr << "***" << f[6][11] << endl;
  printf("%d\n", f[1][n]);
  return 0;
}