P9523 [JOISC 2022] 复制粘贴 3 题解

Description

JOI 公司是一家以“没啥用发明”而闻名的公司。最近，JOI 公司开发了一款名为“没啥用编辑器”的编辑器。

在这个编辑器中，可以执行如下几种操作来输入某个字符串，设 $X$ 为屏幕上的字符串，$Y$ 为剪切板中的字符串，初始均为空串：

• 操作 A：输入字符 $c$，即将 $X$ 更新为 $X+c$。
• 操作 B：选择所有字符并剪切，即将 $Y$ 更新为 $X$，并将 $X$ 置为空串。
• 操作 C：将剪切板中的字符串粘贴到当前字符串末尾，即将 $X$ 更新为 $X+Y$。

对于字符串或字符 $x,y$，$x+y$ 表示将 $x$ 和 $y$ 顺次拼接得到的结果。使用一次操作 A,B,C 分别要花费 $A,B,C$ 单位时间。

你安装了“没啥用编辑器”，并想要尽可能快地输入一个长度为 $N$ 的字符串 $S$。

你需要计算出最少需要花费多少时间。

• $1\leq N\leq 2500$
• $S$ 是一个长度为 $N$ 的小写字母串。
• $1\leq A,B,C\leq 10^9$

Solution

考虑设 $f_{l,r}$ 表示目前屏幕上为 $S_{l,r}$ 的最小代价。

首先有转移：$f_{l,r}\leftarrow\min\{f_{l,r-1}+A,f_{l+1,r}+A\}$。

然后就可以钦定下一步一定是把 $S_{l,r}$ 放进剪切板，然后复制粘贴 $k$ 次。

这里继续钦定复制粘贴时一定以 $l$ 为左端点，即到下一次 B 操作时，状态为 $[l,p]$，且 $[l,p]$ 中包含至少 $k$ 个不相交的 $S_{l,r}$。

考虑枚举 $k$，转化为找到最小 $p$ 满足 $[l,p]$ 包含 $k$ 个互不相交的 $[l,r]$，预处理出 $nxt_{l,r}$ 表示 $r$ 右边第一个与 $S_{l,r}$ 相等的子串的右端点即可。转移如下：$\displaystyle f_{l,p}\leftarrow f_{l,r}+B+C\cdot k+A\cdot \left(p-l+1-k\cdot (r-l+1)\right)$。

下面证明一下为什么第一次复制粘贴一定以 $l$ 为左端点。

归纳证明，先假设长度小于等于 $r-l+1$ 的都满足了条件，那么容易发现对于任意一个 $[pl,pr]$，如果满足 $[pl,pr]$ 内包含至少 $k$ 个 $S_{l,r}$ 且从中删掉左右端点都不满足条件的话，一定存在另一个和 $S_{l,r}$ 相等的串以 $pl$ 为左端点，否则左端点就可以加一。这也就说明了转移一定不会少东西。

时间复杂度：$O(n^2\ln n)$。

Code

#include <bits/stdc++.h>

// #define int int64_t

using i64 = int64_t;
using u64 = uint64_t;

const int kMaxN = 2505;

int n;
int nxt[kMaxN][kMaxN];
i64 A, B, C, f[kMaxN][kMaxN];
u64 hs[kMaxN], pw[kMaxN];
std::string str;

u64 gethash(int l, int r) { return hs[r] - hs[l - 1] * pw[r - l + 1]; }

void prework() {
  pw[0] = 1;
  for (int i = 1; i <= n; ++i) {
    pw[i] = 13331ull * pw[i - 1];
    hs[i] = 13331ull * hs[i - 1] + str[i];
  }
}

void getnxt() {
  std::unordered_map<u64, int> mp;
  for (int i = n; i; --i) {
    for (int j = i; j; --j) {
      u64 hsh = gethash(j, i);
      if (mp.count(hsh)) nxt[j][i] = mp[hsh];
    }
    for (int j = i; j <= n; ++j) mp[gethash(i, j)] = j;
  }
}

void dickdreamer() {
  std::cin >> n >> str >> A >> B >> C;
  str = " " + str;
  prework(), getnxt();
  memset(f, 0x3f, sizeof(f));
  for (int i = 1; i <= n + 1; ++i) f[i][i - 1] = 0;
  for (int len = 1; len <= n; ++len) {
    for (int i = 1; i <= n - len + 1; ++i) {
      int j = i + len - 1;
      f[i][j] = std::min({f[i][j], f[i + 1][j] + A, f[i][j - 1] + A});
      for (int k = 1, p = j; p; ++k, p = nxt[p - len + 1][p]) {
        f[i][p] = std::min(f[i][p], f[i][j] + B + C * k + A * (p - i + 1 - k * len));
      }
    }
  }
  std::cout << f[1][n] << '\n';
}

int32_t main() {
#ifdef ORZXKR
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int T = 1;
  // std::cin >> T;
  while (T--) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  return 0;
}