Serious Business 题解

· · 题解

一种可能更好想的DP方式（？

设 f_x 表示走到 (2,x) 的最小价值，那么答案显然为：

\max\limits_{1\le i \le n}\{f_i+s_i\}

其中 s 为第三行的后缀和。

考虑转移。显然第 x 个格子至少需要被一个区间覆盖，枚举该区间：

f_x=\max\limits_{l_i \le x \le r_i}\{...\}

确定了使用的区间 i 后，有两种可能，即只使用区间 i，或继续使用其他区间。

其中，p_{1/2} 为 1/2 行的前缀和，v_i 为第 i 个区间使用的代价。

带回原式：

f_x=\max\limits_{l_i \le x \le r_i}\{\max(f_{l_i-1}+p_{2,x}-p_{2,l_i-1}-v_i,\max\limits_{l_i \le k\le x}\{p_{1,k}-p_{2,k-1}-v_i+p_{2,x}\})\} =\max\limits_{l_i \le x \le r_i}\{\max(f_{l_i-1}-p_{2,l_i-1}-v_i,\max\limits_{l_i \le k\le x}\{p_{1,k}-p_{2,k-1}-v_i\})\}+p_{2,x}

前面一坨显然可以维护，把区间按 l 排序后依次加入线段树即可。

对于后面那一坨，考虑当区间 i 第一次加入线段树时，一定有 l_i=x，也就是说此时 k 等于 x，即 p_{1,x}-p_{2,x-1}-v_i。

当每次 x+1 时（显然外层循环枚举 x），对于所有 l_i\le x，相当于 k 多了一种取值，即 p_{1,x+1}-p_{2,x}-v_i。

那就再开一棵线段树，存储每个 r=x 位置的 \max\{p_{1,x+1}-p_{2,x}-v_i\} 以及取最大值时 v_i 的值，显然 x+1 更新时 v_i 的值不变，于是就可以比较扭曲地用线段树维护后面那坨东西了。

代码如下：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll inf=1e18;
const int maxn=500010;
const int N=maxn<<2;
inline int read(){
    int x=0,f=1;
    char c=getchar();
    for(;!(c>='0'&&c<='9');c=getchar())
        if(c=='-') f=-1;
    for(;c>='0'&&c<='9';c=getchar())
        x=(x<<1)+(x<<3)+c-'0';
    return x*f;
}
struct Que{
    int l,r,k;
    bool operator <(Que a)const{return l<a.l;}
}a[maxn];
ll data1[N],data2[N],lz[N],K2[N];
ll f[maxn],pm[maxn];
ll p[3][maxn],s[maxn];
int c[4][maxn],n,m;
//K2:当x位置取最大值时,vi的值
//显然pushdown的时候 MIN(K2) 最优 
void Insert1(int i,int l,int r,int x,ll k){
    if(l==r){
        data1[i]=max(data1[i],k);
        return ;
    }
    int mid=l+r>>1;
    if(x<=mid) Insert1(i<<1,l,mid,x,k);
    else Insert1(i<<1|1,mid+1,r,x,k);
    data1[i]=max(data1[i<<1],data1[i<<1|1]);
}
void pushdown(int i){
    if(lz[i]==-inf) return ;
    data2[i<<1]=max(data2[i<<1],lz[i]-K2[i<<1]);
    data2[i<<1|1]=max(data2[i<<1|1],lz[i]-K2[i<<1|1]);
    lz[i<<1]=max(lz[i<<1],lz[i]),lz[i<<1|1]=max(lz[i<<1|1],lz[i]);
    lz[i]=-inf;return ;
}
void Insert2(int i,int l,int r,int x,ll k,int kk){
    if(l==r){
        if(k>data2[i]) data2[i]=k,K2[i]=kk;
        return ;
    }
    pushdown(i);
    int mid=l+r>>1;
    if(x<=mid) Insert2(i<<1,l,mid,x,k,kk);
    else Insert2(i<<1|1,mid+1,r,x,k,kk);
    K2[i]=min(K2[i<<1],K2[i<<1|1]);
    data2[i]=max(data2[i<<1],data2[i<<1|1]);
}
ll Query1(int i,int l,int r,int suf){
    if(r<suf) return -inf;
    if(l>=suf) return data1[i];
    int mid=l+r>>1;
    return max(Query1(i<<1,l,mid,suf),Query1(i<<1|1,mid+1,r,suf));
}
ll Query2(int i,int l,int r,int suf){
    if(r<suf) return -inf;
    if(l>=suf) return data2[i];
    pushdown(i);
    int mid=l+r>>1;
    return max(Query2(i<<1,l,mid,suf),Query2(i<<1|1,mid+1,r,suf));
}
void build(int i,int l,int r){
    data1[i]=data2[i]=lz[i]=-inf,K2[i]=inf;
    if(l==r||l>r) return ;
    int mid=l+r>>1;
    build(i<<1,l,mid),build(i<<1|1,mid+1,r);
}
void Modify(int i,int l,int r,int suf,ll x){
    if(data2[i]==-inf) return ;
    if(l>=suf){
        lz[i]=max(lz[i],x);
        data2[i]=max(data2[i],x-K2[i]);
        return ;
    }
    pushdown(i);
    int mid=l+r>>1;
    if(mid>=suf) Modify(i<<1,l,mid,suf,x);
    Modify(i<<1|1,mid+1,r,suf,x);
    data2[i]=max(data2[i<<1],data2[i<<1|1]);
}
int main(){
    n=read(),m=read();
    for(int i=1;i<=3;i++)
        for(int j=1;j<=n;j++)
            c[i][j]=read();
    for(int j=1;j<=n;j++){
        p[1][j]=p[1][j-1]+c[1][j];
        p[2][j]=p[2][j-1]+c[2][j];
        s[n-j+1]=s[n-j+2]+c[3][n-j+1];
    }
    for(int i=1;i<=m;i++)
        a[i].l=read(),a[i].r=read(),a[i].k=read();
    sort(a+1,a+1+m),build(1,1,n);
    int cnt=1;
    for(int i=1;i<=n;i++){
        Modify(1,1,n,i,p[1][i]-p[2][i-1]);
        while(cnt<=m&&a[cnt].l<=i){
            if(a[cnt].l>1) Insert1(1,1,n,a[cnt].r,f[a[cnt].l-1]-p[2][a[cnt].l-1]-a[cnt].k);
        //注意,如果要用两个区间,那靠前的区间左边界至少要大于1才行(或者给f[0]赋个最大值也行)
            Insert2(1,1,n,a[cnt].r,p[1][i]-p[2][i-1]-a[cnt].k,a[cnt].k),cnt++;
        }       
        f[i]=max(Query1(1,1,n,i),Query2(1,1,n,i))+p[2][i];
    }
    ll ans=-inf;
    for(int i=1;i<=n;i++)
        ans=max(ans,f[i]+s[i]);
    printf("%lld\n",ans);
    return 0;
}

写法虽然很扭曲，但整个思考过程是顺畅的。