[BalticOI 2006 Day 2] RLE COMPRESSION

· · 题解

原题链接

首先对输入的编码进行解码，按照题意模拟即可。解码时需要将相邻的相同字符合并。

设 f_{i,j} 表示处理了前 i 个字符相同的连续段，处理完这个连续段后 e 为 j 的最小长度。

记 c_i 为第 i 个连续段的字符，l_i 为这个连续段的长度，same_i 为当 e=c_i 时压缩这个连续段所需的最小字符数，dif_i 为 e\neq c_i 时压缩这个连续段所需的最小字符数。

则有：

$f_{i,j}=\begin{cases}\min(f_{i-1,j}+same_i,f_{i-1,k\neq j}+dif_i+3),&\text{if}~j=c_i\\f_{i-1,j}+dif_i,&\text{otherwise}\end{cases}

转移相当于枚举在一个连续段后是否将 e 更换为这个连续段的字符（显然若要更换 e，那么将 e 更换为非这个连续段的字符不如更换为这个连续段的字符优）。

这个转移方程状态数是 O(n^2) 的，转移是 O(n) 的，考虑优化。

如果采用线段树优化 DP，采用类似扫描线的方法，每次询问 0-c_i-1，c_i+1-n-1 这两个区间最小值来更新 f_{i,c_i}，区间加更新 0-c_i-1，c_i+1-n-1 两个区间，时间复杂度是 O(m\log n) 的，一般情况下常数较大，难以通过。

可以发现在转移方程中，除了 f_{i,c_i} 以外的所有值都需要加上 dif_i，可以直接全局加上，单独考虑 f_{i,c_i} 即可。

稍作修改后的转移方程如下：

f_{i,j}=\begin{cases}\min(f_{i-1,j}+same_i-dif_i,f_{i-1,k\neq j}+3),&\text{if}~j=c_i\\f_{i-1,j},&\text{otherwise}\end{cases}

这样每次只需要更新 f_{i,c_i} 的值。可以用一个堆来维护 f_{i-1,k} 的最小值，时间复杂度仍然为 O(m\log n)，但是常数要小很多。

由于每次只需要存下当前的 f_i 数组，空间复杂度 O(n)。

实现细节

在最后，需要将 DP 出的最小值加上 \sum dif_i 再输出。

输出方案，由于 f_{i,j!=c_i} 一定是由 f_{i-1,j} 转移来的，所以只需要记录 f_{i,c_i} 的转移。

倒着规划出方案，按照题意输出即可，具体细节可以参考代码。

堆可以这样实现：

堆中每个元素保存 v、t、time 三个变量，其中 v 是 f_{i,j} 的值，t 是 j，time 是放入堆中的时间。记 lst_{k} 为 k 最后一次作为 c_i 的位置，那么将 time<c_i 的元素全部忽略即可。

Code

#include<cstdio>
#include<cctype>
#include<queue>
#include<cstring>
#define mset(arr,val) memset(arr,val,sizeof(arr))
using namespace std;
typedef long long ll;
const int SIZE=2e6+10,EXTRA=4e6+10;
namespace fastIO 
{
    const int B=1<<16;
    char buf[B],*h=buf,*t=buf;
    inline char gc()
    {
        if(h==t)h=buf,t=buf+fread(buf,1,B,stdin);
        return h==t?EOF:*(h++);
    }
    template<typename T>inline void read(T &x) 
    {
        register char ch=gc();x=0;
        while(!isdigit(ch))ch=gc();
        while(isdigit(ch))x =(x<<3)+(x<<1)+(ch^48),ch=gc();
    }
    template<typename T>inline void _print(T x){if(!x)return;_print(x/10),putchar('0'+x%10);}
    template<typename T>inline void print(T x){if(x)return _print(x);putchar('0');}
}
using namespace fastIO;
struct pii{ll v;int t,tag;};
inline bool operator<(pii x,pii y){return x.v>y.v;}
priority_queue<pii>q;
int n,m,a[SIZE],v[SIZE],k[SIZE],top,w[SIZE],cnt,len,wfrom[SIZE],nxt[SIZE],ths,dp[SIZE],close[SIZE],sum;
ll real[SIZE];
inline ll same(ll x){return 3*(x/n+(x%n==0?0:1));}
inline ll dif(ll x)
{
    if(x<3)return x;
    ll res=3*(x/(n+2)-(x%(n+2)==0?1:0));
    x-=(n+2)*(x/(n+2)-(x%(n+2)==0?1:0));
    res+=min(3ll,x);
    return res;
}
inline void pop_legacy(){while(!q.empty()&&q.top().tag<close[q.top().t])q.pop();}
int main()
{
    read(n),read(m);
    for(int i=1;i<=m;i++)read(a[i]);
    for(int i=1,e=0;i<=m;i++)
    {
        if(a[i]==e)
        {
            if(a[i+1]==e)v[++top]=e,k[top]=a[i+2]+1;
            else if(a[i+1]!=e)
            {
                if(a[i+2]==0)e=a[i+1];
                else v[++top]=a[i+1],k[top]=a[i+2]+3;
            }
            i+=2;
        }
        else v[++top]=a[i],k[top]=1;
    }
    w[cnt]=-1;
    for(int i=1;i<=top;i++)
    {
        if(v[i]!=w[cnt])w[++cnt]=v[i];
        real[cnt]+=k[i];
    }
    q.push({0,0,0});
    for(int i=1;i<n;i++)dp[i]=3,q.push({3,i,0});
    for(int i=1,SAME,DIF;i<=cnt;i++)
    {
        pii val;SAME=same(real[i]),sum+=(DIF=dif(real[i]));
        pop_legacy(),val=q.top();
        if(val.t==w[i])q.pop(),pop_legacy(),val=q.top();
        close[w[i]]=i;
        if(dp[w[i]]+SAME-DIF<val.v+3)dp[w[i]]=dp[w[i]]+SAME-DIF,wfrom[i]=w[i];
        else dp[w[i]]=val.v+3,wfrom[i]=val.t;
        q.push({dp[w[i]],w[i],i});
    }
    print(sum+q.top().v),putchar('\n');
    ths=q.top().t;
    for(int i=cnt;~i;i--){nxt[i]=ths;if(ths==w[i])ths=wfrom[i];}
    ths=0;
    if(nxt[0]!=ths)print(ths),putchar(' '),print(nxt[0]),putchar(' '),putchar('0'),putchar(' '),ths=nxt[0];
    for(int i=1;i<=cnt;i++)
    {
        if(ths==w[i])
        {
            while(real[i]>=n){print(ths),putchar(' '),print(w[i]),putchar(' '),print(n-1),putchar(' '),real[i]-=n;if(real[i]<n)break;}
            if(real[i]>0)print(ths),putchar(' '),print(w[i]),putchar(' '),print(real[i]-1),putchar(' ');
        }
        else 
        {
            while(real[i]>=n+2){print(ths),putchar(' '),print(w[i]),putchar(' '),print(n-1),putchar(' '),real[i]-=n+2;if(real[i]<n+2)break;}
            if(real[i]<=3)for(int j=1;j<=real[i];j++)print(w[i]),putchar(' ');
            else print(ths),putchar(' '),print(w[i]),putchar(' '),print(real[i]-3),putchar(' ');
        }
        if(nxt[i]!=ths)print(ths),putchar(' '),print(nxt[i]),putchar(' '),putchar('0'),putchar(' '),ths=nxt[i];
    }
    return 0;
}