题解：P16043 [ICPC 2022 NAC] Cram

· · 题解

题意简述

编码一个字符需要 1 字节。也可以用固定 3 字节的回溯引用复制前面出现过的字符串，且来源和目标允许重叠。求编码整个字符串的最小代价。

解题思路

设当前位置为 i，来源位置为 j<i。允许重叠意味着引用长度只需满足两段字符相等，不必限制在距离 i-j 以内。

记从 i 开始能够引用的最长长度为：

L_i=\max_{0\le j<i}\operatorname{lcp}(s[i\mathbin{\ldotp\ldotp}],s[j\mathbin{\ldotp\ldotp}])

只要知道全部 L_i，位置 i 就能用一次引用到达任意 i+1 到 i+L_i。

先建立后缀数组、排名数组和相邻后缀的最长公共前缀数组。若两个后缀的排名为 x<y，它们的最长公共前缀等于：

\min_{x<k\le y}\operatorname{height}_k

使用线段树维护区间最小值即可回答这个查询。

按起点 i 从左到右处理后缀，并把已经处理过的后缀排名放入有序集合。当前排名与任意更远排名之间的 height 查询区间，都包含与同方向最近排名的查询区间。区间最小值不会因扩大区间而增加，所以最大最长公共前缀一定由集合中的排名前驱或后继取得。每个 L_i 只需至多两次查询。

接下来计算最小编码代价。令 f_i 表示编码前 i 个字符的最小代价。直接输出字符给出：

f_{i+1}\le f_i+1

在位置 i 使用引用，则候选值 f_i+3 会覆盖整个终点区间 [i+1,i+L_i]。

这些区间候选不需要小根堆。首先，f_i 单调不降：任意一个前缀的最优编码都可以删去最后一个字符；若最后一个编码单位是长度大于 1 的引用，就把它缩短一位。所得编码仍合法，所以 f_i\le f_{i+1}。

因此，按位置产生的候选值 f_i+3 也单调不降。将候选值和最远终点依次放入普通队列。计算 f_{i+1} 前，持续删除队首中最远终点小于 i+1 的候选。若队列非空，队首就是仍覆盖当前位置的最小候选值。

后缀数组、集合插入和线段树查询需要 O(n\log n) 时间；队列中每个候选至多进出一次，DP 为 O(n)。总时间复杂度为 O(n\log n)，空间复杂度为 O(n)。

正确性证明

对任意位置 i，L_i 枚举了所有更早后缀与当前后缀的最长公共前缀最大值。排名同侧的更远后缀对应更大的 height 区间，其区间最小值不可能超过最近后缀，所以只查询前驱和后继不会漏掉最优来源。

直接字符转移覆盖最后一个编码单位为普通字符的方案。每个从 i 产生的区间候选覆盖所有合法引用长度，因此也覆盖最后一个编码单位为回溯引用的全部方案。这两类恰好包含所有编码方式。

由于 f_i 单调不降，候选值按入队顺序单调不降。删除所有已经失效的队首后，队首必为仍有效候选中的最小值。故每一步得到的 f_{i+1} 都是所有合法最后一步转移的最小代价，最终 f_n 即为答案。

参考代码

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

using pii=pair<int,int>;
const int N=100005;
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]);
    }
    queue<pii> q;
    for(int i=0;i<n;i++)
    {
        if(len[i])q.push({f[i]+3,i+len[i]});
        while(!q.empty()&&q.front().second<i+1)q.pop();
        f[i+1]=f[i]+1;
        if(!q.empty())f[i+1]=min(f[i+1],q.front().first);
    }
    cout<<f[n]<<'\n';
    return 0;
}