题解：P16043 [ICPC 2022 NAC] Cram

· · 题解

题意简述

原字符的编码代价为 1，回溯引用的代价固定为 3，且允许引用区间重叠。求给定字符串的最小编码代价。

解题思路

设 l_i 为从位置 i 开始，能与某个更早后缀匹配的最长长度。回溯允许重叠，因此只需比较原串中的两个后缀，无须限制匹配段的终点。

先求后缀数组和相邻后缀的最长公共前缀。按起点从左到右插入后缀排名。对当前排名而言，与已插入排名的最大最长公共前缀，一定由排名前驱或后继取得。理由是跨过一个更近排名后，区间内相邻最长公共前缀的最小值不会增大。用线段树查询排名区间最小值，即可求出全部 l_i。

令 f_i 表示编码前 i 个字符的最小代价。输出一个原字符会转移到 f_{i+1}。在位置 i 使用回溯时，任意终点 j\in[i+1,i+l_i] 都能以代价 f_i+3 到达。用小根堆保存这些转移及其最晚终点。处理 f_i 前删去已过期转移，堆顶就是所有仍覆盖 i 的最小代价。

后缀数组、集合插入和区间查询的总复杂度为 O(n\log n)，空间复杂度为 O(n)。

题目数据使用 CRLF 换行，getline 在部分环境下会保留行末的 \r，读入后需要将其删除，否则会被误认为正文字符。

参考代码

#include <bits/stdc++.h>
using namespace std;

using pii=pair<int,int>;
const int N=100005;
const int inf=0x3f3f3f3f;
int sa[N],rk[N],tmp[N],cnt[N],ht[N],tr[N<<2],len[N],f[N];
string s;
void get_sa()
{
    int n=s.size();
    for(int i=0;i<n;i++)rk[i]=(unsigned char)s[i];
    int m=256;
    fill(cnt,cnt+m,0);
    for(int i=0;i<n;i++)cnt[rk[i]]++;
    for(int i=1;i<m;i++)cnt[i]+=cnt[i-1];
    for(int i=n-1;i>=0;i--)sa[--cnt[rk[i]]]=i;
    if(n==1)
    {
        rk[0]=0;
        return;
    }
    for(int k=1,p;k<n;k<<=1)
    {
        p=0;
        for(int i=n-k;i<n;i++)tmp[p++]=i;
        for(int i=0;i<n;i++)if(sa[i]>=k)tmp[p++]=sa[i]-k;
        fill(cnt,cnt+m,0);
        for(int i=0;i<n;i++)cnt[rk[tmp[i]]]++;
        for(int i=1;i<m;i++)cnt[i]+=cnt[i-1];
        for(int i=n-1;i>=0;i--)sa[--cnt[rk[tmp[i]]]]=tmp[i];
        swap(rk,tmp);
        p=1;
        rk[sa[0]]=0;
        for(int i=1;i<n;i++)
        {
            int x=sa[i-1],y=sa[i];
            rk[y]=tmp[x]==tmp[y]&&(x+k<n?tmp[x+k]:-1)==(y+k<n?tmp[y+k]:-1)?p-1:p++;
        }
        if(p==n)break;
        m=p;
    }
    for(int i=0,k=0;i<n;i++)
    {
        if(!rk[i])
        {
            k=0;
            continue;
        }
        int j=sa[rk[i]-1];
        while(i+k<n&&j+k<n&&s[i+k]==s[j+k])k++;
        ht[rk[i]]=k;
        if(k)k--;
    }
}
int query(int x,int y,int siz)
{
    if(x>y)swap(x,y);
    int ans=N;
    for(x+=siz+1,y+=siz+1;x<y;x>>=1,y>>=1)
    {
        if(x&1)ans=min(ans,tr[x++]);
        if(y&1)ans=min(ans,tr[--y]);
    }
    return ans;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    getline(cin,s);
    if(!s.empty()&&s.back()=='\r')s.pop_back();
    get_sa();
    int n=s.size(),siz=1;
    while(siz<n)siz<<=1;
    fill(tr,tr+(siz<<1),N);
    for(int i=0;i<n;i++)tr[siz+i]=ht[i];
    for(int i=siz-1;i;i--)tr[i]=min(tr[i<<1],tr[i<<1|1]);
    set<int> st;
    for(int i=0;i<n;i++)
    {
        auto it=st.lower_bound(rk[i]);
        if(it!=st.end())len[i]=max(len[i],query(rk[i],*it,siz));
        if(it!=st.begin())len[i]=max(len[i],query(rk[i],*prev(it),siz));
        st.insert(rk[i]);
    }
    fill(f,f+n+1,inf);
    f[0]=0;
    priority_queue<pii,vector<pii>,greater<pii>> q;
    for(int i=0;i<=n;i++)
    {
        while(!q.empty()&&q.top().second<i)q.pop();
        if(!q.empty())f[i]=min(f[i],q.top().first);
        if(i==n)break;
        f[i+1]=min(f[i+1],f[i]+1);
        if(len[i])q.push({f[i]+3,i+len[i]});
    }
    cout<<f[n]<<'\n';
    return 0;
}