题解：U633098 请输入文本

XuHenry · 2025-11-18 19:41:04 · 题解

暴力

随便怎么做都可以，不具体阐述。

朴素 DP

设 dp_i 表示打出前 i 个字符的最小耗时，则有：

其中 S 从 1 开始， S_{[l,r]} 表示 S 从第 l 个字符到第 r 个字符的子串。

直接做这个 DP 是 \mathcal{O}(n^3) 的，需要优化。

非正解 DP 优化

考虑到字符串，直接使用 hash 可以优化到 \mathcal{O}(n^2)。然后我们又可以发现单调性，于是再加一个二分就可以优化到 \mathcal{O}(n\log n)。已经很接近了，但是我们需要 \mathcal{O}(n) 的算法，这可如何是好？

周期性

当你就差临门一脚时，不妨静下心来，回过头再看一看题。“周期性”，这是题目的唯一一个特殊性质，可以作为我们的突破口。

如果 S 有周期性的话，那么我们就可以 \mathcal{O}(n) 求出周期，然后直接倍增周期做到 \mathcal{O}(\log n)……等等，\mathcal{O}(n) 怎么求出周期？用 KMP 的话，好像可以直接用在 DP 上！

KMP 优化 DP

回看转移中的 S_{[j+1,i]}=S_{[1,i-j]}，我们会惊讶地发现这与 KMP 几乎相同！（当然如果你熟练的话肯定一眼就看出来了。）再考虑到“周期性”，我们可以对于前 i 个字符直接用 KMP \mathcal{O}(n) 预处理出它的“周期” i-\text{kmp}(i)，然后就可以直接通过计算“周期”得到最佳转移点了！具体的，我们先算出最少（指向上取整）需要几个“周期”可以完全将前 i 个字符覆盖，再取一多半（指向上取整）的“周期”就找到这个转移点了，时间复杂度 \mathcal{O}(n)！

注：这里的“周期”指的是可以由某个子串重复多次并取其子串构成，即“不完全周期”。

补充

• 这道题有求出“周期”的方法，可供参考。
• 感谢 @gaozeju 提供的思路：这道题有直接求出最佳转移点的方法，大概就是暴力跳 kmp 的优化，可以直接套用。

  参考代码

  “周期性”法：

  for(int i = 1, j = 0; i < n; ++i) {
  while(j && s[i] != s[j]) j = kmp[j];
  if(s[i] == s[j]) ++j;
  kmp[i + 1] = j;
  }
  for(int i = 1; i <= n; ++i) {
  dp[i] = dp[i - 1] + t0[s[i - 1] - 'a'];
  const int x = i - kmp[i];
  if(x) {
      const int j = ((i + x - 1) / x + 1) / 2 * x;
      dp[i] = min(dp[i], dp[j] + t1 + 1LL * t2 * (2 * j - i));
  }
  }
  cout <<dp[n] <<'\n';

  “转移点”法：

  for(int i = 1, j = 0; i < n; ++i) {
  while(j && s[i] != s[j]) j = kmp[j];
  if(s[i] == s[j]) ++j;
  kmp[i + 1] = j;
  }
  dp[0] = t0[s[0] - 'a'];
  for(int i = 1, j = 0; i < n; ++i) {
  dp[i] = dp[i - 1] + t0[s[i] - 'a'];
  while(j && s[i] != s[j]) j = kmp[j];
  if(s[i] == s[j]) ++j;
  while(j << 1 > i + 1) j = kmp[j];
  if(j) dp[i] = min(dp[i], dp[i - j] + t1 + 1LL * t2 * (i + 1 - 2 * j));
  }
  cout <<dp[n - 1] <<'\n';