P9871 [NOIP2023] 天天爱打卡题解

· · 题解

Link

设 f_i 表示以第 i 天作为某一段连续跑步的最后一天，设 g_i=\max_{j=1}^if_i ，那么有转移方程 f_i=\max_{j=i-k+1}^i g_{j-2}+w(j,i)-d(i-j+1) ，也即 f_i=\max_{j=i-k+1}^i g_{j-2}+w(j,i)-(i+1)\times d+j\times d)。

相当于枚举这段区间的左端点。w(l,r) 表示从第 l 天跑到第 r 天能获得的能量补充。

第一项与最后一项可以直接取最值，第三项只跟 i 有关无需考虑，中间那个 w(l,r) 可以用扫描线维护。

但是跑步天数是 n ，非常大，所以只能离散化。考虑到某一段跑步的最后一天一定是一个任务的完成日期，只保留这一天，为了方便扫描线也保留每个任务的开始日期。

转移的时候要注意那个 g_{j-2} ，离散化后其实是把在 i 前面且最后一个不与 i 相邻的下标 x 放到 i 上，可以特判 i-1 是否合法或直接二分。

注意转移顺序， i 是可以从 i 转移的，但 f_i 只会从比 i 小的位置转移。

我在实现的时候把 f 和 g 合并在一起了，感觉读起来更难也更容易出错，不建议合在一起写。

特别注意，在扫描线的时候，两维都是可以离散化的，但在枚举其中一维的时候要记得这一维有没有离散化，我就因为两维都离散化但却在枚举的时候判断的是离散化前的数字导致第一组大样例过不去（

code

const int N=2e5+5;

int X[N],len;

//线段树实现了区间加，清空和区间查，为了美观不放上来了

struct upd{
    ll l,r,x,w;
    bool operator<(upd ano)const{
        return x<ano.x;
    }
}Q[N];
int tot;

ll f[N];

int x[N],y[N],w[N];

signed main(){
    signed c=read(),_T=read();
    while(_T--){
        len=tot=0;
        int n=read(),m=read(),k=read();ll d=read();
        for(int i=1;i<=m;i++){
            x[i]=read(),y[i]=read(),w[i]=read();
            X[++len]=x[i],X[++len]=x[i]-y[i]+1;
        }
        sort(X+1,X+1+len);
        len=unique(X+1,X+1+len)-X-1;
        for(int i=1;i<=m;i++){
            int l=lower_bound(X+1,X+1+len,x[i]-y[i]+1)-X;
            int r=lower_bound(X+1,X+1+len,x[i])-X;
            Q[++tot]={1,l,r,w[i]};//就是这里，r是要枚举的那一维，我在这里存的是离散化后的值，但在后面判断却用了离散化前的值
        }
        sort(Q+1,Q+1+tot);
        for(int i=1,j=1;i<=len;i++){
            int lst=lower_bound(X+1,X+1+len,X[i]-1)-X-1;
            T.update(1,1,len,i,i,f[lst]+X[i]*d);//更新第i个点的贡献

            while(j<=tot&&Q[j].x==i)//这里是Q[j].x==i而不是Q[j].x==X[i]，就是上面说的离散化前与后的问题。
                T.update(1,1,len,Q[j].l,Q[j].r,Q[j].w),j++;//扫描线

            int frm=lower_bound(X+1,X+1+len,X[i]-k+1)-X;
            f[i]=max(f[i-1],T.query(1,1,len,frm,i)-X[i]*d-d);//取最值
        }print(f[len]),pc('\n');
        T.init(1,1,len);
    }
    return 0;
}