SWERC 2018 K. Dishonest Driver - ツバサの備忘録

解法

区間DPをします。
$dp[i][j] = [i,j)$ の区間に対する最小コスト
とすると、
$dp[i][j] = min(dp[i][k] + dp[k][j])$
になります。ただし、 $[i,k)$ の文字列を複数回連結すると $[i,j)$ になる場合のみ、
$dp[i][j] = min(dp[i][k])$
になります。
この複数回連結、という判定はKMPの周期判定を用いると上手くできます(下のブログ参考)。
ただし、ぴったり複数回連結した場合のみなので、 $(j-i) % (k-i)$ が0にならなければなりません。

snuke.hatenablog.com

#include <bits/stdc++.h>
#define inf (long long)1e7
using namespace std;
 
// A[i]: S[0,i-1] longest match(pre and suf)
struct KMP {
  vector<long long> A;
  long long n;
  string s;
  KMP(string _s = "") {
    s = _s;
    n = s.size();
    A.assign(n + 1, 0);
    A[0] = -1;
    for(int i = 0, j = -1; i < n; ++i) {
      while(j >= 0 && s[i] != s[j]) j = A[j];
      ++j;
      // if(i + 1 < n && s[i + 1] == s[j])
      //   A[i + 1] = A[j];
      // else
      A[i + 1] = j;
    }
  }
  inline const long long &operator[](int k) const {
    return (A[k]);
  }
  vector<long long> calccycle() {
    vector<long long> res(n, 0);
    for(int i = 0; i < n; ++i) res[i] = i + 1 - A[i + 1];
    return res;
  }
};
 
long long n;
string s;
vector<vector<long long>> dp;
 
long long solve(long long l, long long r);
 
int main() {
  cin >> n >> s;
  vector<long long> v = KMP(s).calccycle();
  dp.assign(n + 1, vector<long long>(n + 1, inf));
  for(int i = 0; i < n; ++i) dp[i][i + 1] = 1;
  for(int i = 0; i <= n; ++i) dp[i][i] = 0;
  cout << solve(0, n) << endl;
  return 0;
}
 
long long solve(long long l, long long r) {
  if(dp[l][r] != inf) return dp[l][r];
  long long res = r - l,
            cycle = KMP(s.substr(l, r - l))
                        .calccycle()[r - l - 1];
 
  for(int i = l + 1; i < r; ++i) {
    long long now = solve(l, i);
    if((r - l) % cycle != 0 || cycle > i - l ||
       (i - l) % cycle != 0)
      now += solve(i, r);
    res = min(res, now);
  }
  return dp[l][r] = res;
}