专栏文章

题解：U633098 请输入文本

XXuHenry
题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min5jpjg
此快照首次捕获于
2025/12/01 20:55
3 个月前
此快照最后确认于
2025/12/01 20:55
3 个月前
查看原文

暴力

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

朴素 DP

设 dpidp_i 表示打出前 ii 个字符的最小耗时，则有： dpi=min⁡{dpi−1+t0Simin⁡⌈i2⌉≤j<i,S[j+1,i]=S[1,i−j](dpj+t1+(2j−i)t2)dp_i=\min\begin{cases}dp_{i-1}+t_{0_{S_i}}\\\min_{\lceil \frac{i}2\rceil \le j<i,S_{[j+1,i]}=S_{[1,i-j]}}(dp_j+t_1+(2j-i)t_2)\end{cases} 其中 SS 从 11 开始， S[l,r]S_{[l,r]} 表示 SS 从第 ll 个字符到第 rr 个字符的子串。
直接做这个 DP 是 O(n3)\mathcal{O}(n^3) 的，需要优化。

非正解 DP 优化

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

周期性

当你就差临门一脚时，不妨静下心来，回过头再看一看题。“周期性”，这是题目的唯一一个特殊性质，可以作为我们的突破口。
如果 SS 有周期性的话，那么我们就可以 O(n)\mathcal{O}(n) 求出周期，然后直接倍增周期做到 O(log⁡n)\mathcal{O}(\log n)……等等，O(n)\mathcal{O}(n) 怎么求出周期？用 KMP 的话，好像可以直接用在 DP 上！

KMP 优化 DP

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

补充

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

参考代码

“周期性”法：
CPP
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';
“转移点”法：
CPP
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';

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...