P9744 消除序列 题解

本题有多种解法，我这里先讲一个我的考场做法吧。

切入点

我们发现我们至多使用一次操作一，而剩下部分的 \(0\) 肯定是依靠操作二补全，操作三的作用只是用来填补操作一的空白的，所以我们发现我们对一个序列的操作一定是前一段用操作一和操作三，后一段用操作二。

思路1

一开始考虑暴力 \(O(n)\) 枚举其断点，用个前缀和和后缀和优化即可做到 \(O(nq)\)，拿到 \(60\) 分的好成绩。

\(60pts\ Code\)

int n,a[N],b[N],c[N],q,m;
ll pre[N],sub[N];
bool p[N];
int main(){
    n=read();
    for(int i=1;i<=n;i++)a[i]=read();
    for(int i=1;i<=n;i++)b[i]=read();
    for(int i=1;i<=n;i++)c[i]=read();
    q=read();
    while(q--){
        m=read();
        for(int i=1;i<=n;i++)p[i]=0,pre[i]=sub[i]=0;
        for(int i=1;i<=m;i++)p[read()]=1;
        for(int i=1;i<=n;i++)pre[i]=pre[i-1]+(p[i]?c[i]:0);
        for(int i=n;i;--i)sub[i]=sub[i+1]+(p[i]?0:b[i]);
        ll ans=1e18;
        for(int i=0;i<=n;i++)ans=min(ans,pre[i]+a[i]+sub[i+1]);
        printf("%lld\n",ans);
    }
}

发现瓶颈在于枚举的是 \(n\)，而其实我们用的前缀和和后缀和在 \(p_i\) 和 \(p_{i+1}\) 之间是不受干扰的，所以考虑如何把复杂度降到 \(O(\sum m)\)。
我们令 \(C_i\) 表示前 \(i\) 个 \(c_{p_i}\) 之和，\(B_i\) 表示除去 \(p_i,p_{i+1},\sim p_{m}\) 的所有 \(b_{j}\) 之和，\(preb_{i}\) 表示 \(b_i\) 的前缀和，那么我们不难发现对于 \(x\in[p_i,p_{i+1})\) 来说，\(ans=min\{ans,C+B-preb_x+a_x\}\)，而 \(a_x-preb_x\) 的最小值我们可以用诸如线段树和 st 表的数据结构来维护，这样可以做到 \(O(n\log n)\) 级别的复杂度。
有个细节特别要注意就是我们不选 \(a_i\) 相当于是从 \(p_0\) 开始，所以建 st 表的时候要注意是 \(k\le \log_2 (n+1)\)。

\(Code1\)

const int N=500005;
int n,q,m,p[N],lg[N];
ll a[N],b[N],c[N],preb[N],st[20][N];
int main(){
    n=read();
    for(int i=2;i<=n+1;i++)lg[i]=lg[i>>1]+1;//n+1
    for(int i=1;i<=n;i++)a[i]=read();
    for(int i=1;i<=n;i++)st[0][i]=a[i]-(preb[i]=preb[i-1]+(b[i]=read()));
    for(int i=1;i<=n;i++)c[i]=read();
    for(int k=1;k<=lg[n+1];k++)//lg[n+1]
        for(int i=0;i+(1<<k)-1<=n;i++)//一定要从0开始！！
            st[k][i]=min(st[k-1][i],st[k-1][i+(1<<k-1)]);
    q=read();
    while(q--){
        m=read();
        ll B=preb[n],C=0,ans=1e18;
        for(int i=1;i<=m;i++)p[i]=read(),B-=b[p[i]];
        p[m+1]=n+1;
        for(int i=0;i<=m;i++){
            //ans=min(ans,(C+=c[p[i]])+a[p[i]]+((B+=b[p[i]])-preb[p[i]]));
            C+=c[p[i]],B+=b[p[i]];
            int l=p[i],r=p[i+1]-1,k=lg[r-l+1];
            ll w=min(st[k][l],st[k][r-(1<<k)+1]);
            ans=min(ans,w+C+B);
        }
        printf("%lld\n",ans);
    }
    return 0;
}

思路2

上面的方法还是比较复杂了，我们考虑不枚举分界点而是考虑用递推优化这一过程。用 \(f_i\) 表示让前 \(i\) 个变 \(0\) 的最小代价，然后同样因为在相邻的 \(p_i\) 之间值是不受影响的，所以我们枚举 \(p_i\)，其前面用 \(f_i\) 后面都用 \(b_i\) 算代价，复杂度 \(O(\sum m)\)。
具体细节看代码：

\(Code2\)

const int N=500005;
int n,q,m,p[N];
ll a[N],b[N],c[N],f[N],sub[N],bac[N];
int main(){
    n=read();
    for(int i=1;i<=n;i++)a[i]=read();
    for(int i=1;i<=n;i++)f[i]=min(f[i-1]+(b[i]=read()),a[i]);
    for(int i=1;i<=n;i++)c[i]=read();
    for(int i=n;i;--i)sub[i]=sub[i+1]+b[i];
    q=read();
    while(q--){
        m=read();
        for(int i=1;i<=m;i++)p[i]=read();
        bac[m+1]=0;
        for(int i=m;i;--i)bac[i]=bac[i+1]+b[p[i]];
        ll ans=1e18,C=0;
        for(int i=1;i<=m;C+=c[p[i]],i++)
            ans=min(ans,f[p[i]-1]+C+sub[p[i]]-bac[i]);
        printf("%lld\n",min(ans,f[n]+C));
    }
    return 0;
}