题解 [ARC081E] Don't Be a Subsequence

· · 题解

子序列自动机是什么？广搜又是什么？

这不是一个很显然的动态规划吗。

题意

参见题意翻译。

分析

设 f_i 表示以 A_i 开头的子序列不在 A_{i \sim \vert A \vert} 中出现的最小长度，g_i 表示上一个决策点。

设字符 x 第一次出现的位置为 p_x，那么 f_i = 1 + \min\limits_{x} f_{p_x}。

具体实现是容易的，详见代码，时间复杂度 O(\vert A \vert)。

代码

//the code is from chenjh
#include<cstdio>
#include<cstring>
#define MAXN 200035
using namespace std;
char s[MAXN];
int n,f[26],g[MAXN],p[26];
int main(){
    scanf("%s",s+1),n=strlen(s+1);
    for(int x=0;x<26;x++) s[p[x]=++n]=x+'a';//为了减少特判，在字符串最后人为添加 26 个字母。
    for(int i=n-26;i>=0;--i){
        g[i]=*p;//默认后继决策点为 a。
        for(int x=1;x<26;x++)if(f[x]<f[s[g[i]]-'a']) g[i]=p[x];//枚举第后继决策点，如果答案更小就更新。
        i&&(f[s[i]-'a']=f[s[g[i]]-'a']+1,p[s[i]-'a']=i);//转移并更新字符出现的第一个位置。
    }
    for(int x=*g;x;x=g[x]) putchar(s[x]);//从前往后依次输出。
    return 0;
}