P3426 [POI2005]SZA-Template - 洛谷 - 计算机科学教育新生态">P3426 [POI2005]SZA-Template - 洛谷 - 计算机科学教育新生态"> 洛谷 - P3426 - [POI2005]SZA-Template - TonyYin
洛谷 – P3426 – [POI2005]SZA-Template

题目链接:P3426 [POI2005]SZA-Template – 洛谷 – 计算机科学教育新生态

设 $\operatorname{dp}[i]$ 表示前缀 $[1, i]$ 的答案,设 $\operatorname{lst}[i]$ 表示以前缀 $[1, i]$ 为印章,最远能覆盖到的位置。

容易发现,前缀 $[1, i]$ 一定能被自己覆盖,因此 $\operatorname{dp}[i]$ 最大为 $i$。

其何时能被更短的段覆盖?

考虑其 $\rm{border}$,我们以覆盖其 $\rm{border}$ 相同的方式,也就是以 $\operatorname{dp}[\operatorname{border}[i]]$ 为印章长度,尝试覆盖 $[1, i]$。

如果可行,那么 $\operatorname{dp}[i]=\operatorname{dp}[\operatorname{border}[i]]$。

判断可行?

可行当且仅当:$\operatorname{lst}[\operatorname{dp}[\operatorname{border}[i]]] >= i – \operatorname{border}[i]$.

意思就是,以 $\operatorname{dp}[\operatorname{border}[i]]$ 为印章长度,至少要可以覆盖到 $i – \operatorname{border}[i]$。

$[i – \operatorname{border}[i], i]$ 这段与 $[1, \operatorname{border}[i]]$ 完全相同,一定能被覆盖,所以只需 $[i-\operatorname{border}[i]]$ 之前能被覆盖。

#include <bits/stdc++.h>
using namespace std;
const int MAXLEN  = 5e5 + 10;
char s[MAXLEN];
int len, nxt[MAXLEN];
void get_border() {
    nxt[1] = 0;
    for(int i = 2; i <= len; i++) {
        int match = nxt[i - 1];
        while(s[i] != s[match + 1] && match != 0) match = nxt[match];
        if(s[i] == s[match + 1]) match++;
        nxt[i] = match;
    }
}
int dp[MAXLEN]; //dp[i]表示前缀[1, i]的答案
int lst[MAXLEN]; //lst[i]表示以前缀[1, i]为印章,最远能覆盖到的位置
int main() {
    scanf("%s", (s + 1)); len = strlen(s + 1);
    get_border();
    dp[1] = 1; lst[1] = 1;
    for(int i = 2; i <= len; i++) {
        dp[i] = i;
        if(lst[dp[nxt[i]]] >= i - nxt[i]) dp[i] = dp[nxt[i]];
        lst[dp[i]] = i;
    }
    cout << dp[len] << endl;
    return 0;
}
暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇