自动搬运

查看原文

来自洛谷，原作者为

	FQ04gty Let me be cruel, not unnatural.

搬运于2025-08-24 22:31:48，当前版本为作者最后更新于2022-10-13 21:41:20，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

原题链接

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

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

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

则有：

$same_i=3\cdot\lceil\frac{l_i}{n}\rceil$，$dif_i=3\cdot(\lfloor\frac{l_i}{n+2}\rfloor+\min(l_i\bmod (n+2),3))$。

$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;
}