自动搬运

查看原文

来自洛谷，原作者为

	未来姚班zyl 欢迎加入粉丝团！https://www.luogu.com.cn/team/72518|AFO

搬运于2025-08-24 22:52:36，当前版本为作者最后更新于2023-11-21 12:56:32，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

前言

本人在赛时可以说是按照出题人设计的部分分一步一步想到正解，思维过程应该算非常标准，且很多部分分的代码也在赛时打出来了。

所以这篇题解肯定能做到流畅，详细，具体。

题目大意

一共有 $n$ 天，大 Y 可以花费 $d$ 的能量在任何一天跑步，但大 Y 不能在连续的 $k$ 天跑步。

此外，将给出 $m$ 段任务区间 $[l_i,r_i]$。如果在这段区间的每一天都跑了步，则会获得 $v_i$ 的能量。

大 $Y$ 的初始能量为 $0$，请你最大化跑完步后大 Y 最终的能量。

题目分析

以下复杂度均省略了 $T$，即数据组数。

• 我会暴力枚举！

直接枚举每一天是否跑了步，然后计算贡献即可。

复杂度 $O(2^n(n+m))$，期望得分 $8$ 分。

这一部分没什么太大用处，代码也很好写，故不给出代码。

• 我会 dp ！

如果我们知道了在一段区间内都跑了步，我们则可以直接枚举 $m$ 个区间并计算出对答案的贡献。所以我们设计状态 $dp_{i}$，表示只考虑前 $i$ 天的最大答案。首先有转移 $dp_i=dp_{i-1}$。其次，我们考虑右端点为 $i$ 的区间。暴力枚举左端点 $j$（注意区间长度不能超过 $k$），则我们有转移：

$dp_i=\max(dp_i,dp_{j-2}-(i-j+1)d+w_{j,i})$。

其中 $w_{l,r}$ 表示任务区间对 $[l,r]$ 的贡献，可以 $O(m)$ 单次计算。加上 $O(n)$ 枚举左端点，可以做到 $O(nmk)$。

期望得分 $16$ 分。

这一部分代码如下：

ll dp[N];
inline ll get(int l,int r){
	ll ans=0;
	rep(i,1,m)if(a[i].l>=l&&a[i].r<=r)ans+=a[i].k;
	return ans;
}//计算贡献
inline ll got(int x){
	//由于 j-2 可能越界，但并非无法转移，故我们额外写一个函数表示 dp 的值
	if(x>=0)return dp[x];
	return 0;
}
inline void subtask1(){
	rep(i,0,n)dp[i]=0;
	//初始化
	rep(i,1,n){
		rep(j,max(i-k+1,1),i)dp[i]=max(dp[i],get(j,i)+got(j-2)-1LL*d*(i-j+1));//状态转移
		dp[i]=max(dp[i],dp[i-1]);
	}
	cout <<dp[n]<<'\n';
}

• 我会扫描线和树状数组！

我们考虑优化计算贡献的方式。

可以想到，对于枚举的区间 $[j,i]$，能够贡献答案的任务区间 $[l_k,r_k]$ 一定满足 $j\le l_k\le r_k\le i$。

那么我们按照右端点顺序把任务区间加入，则 $r_k\le i$ 的条件就能天然满足。计算贡献时，我们就只需要查询满足 $l_k\ge j$ 的任务区间的权值和即可，这个可以用树状数组维护，单次计算贡献的复杂度降至 $O(\log m)$。

复杂度 $O(nk \log m)$，期望得分 $36$ 分。

这一部分代码如下：

vector<Pi >p[N];//这个存的任务区间 
ll t[N];
inline void add(int x,int k){
	x=n-x+1;//这里直接倒着存，写的时候就不用差分了，下面一样的道理
	while(x<=n)t[x]+=k,x+=x&-x;
}
inline ll query(int x){
	ll ans=0;
	x=n-x+1;
	while(x)ans+=t[x],x-=x&-x;
   return ans;
}//树状数组
#define E(x) for(auto y:p[x])
inline void subtask2(){
	rep(i,1,m)p[a[i].r].pb({a[i].l,a[i].k});
	rep(i,0,n)dp[i]=0;//初始化
	rep(i,1,n){
		E(i)add(y.first,y.second);
		rep(j,max(i-k+1,1),i)dp[i]=max(dp[i],query(j)+got(j-2)-1LL*d*(i-j+1));
		dp[i]=max(dp[i],dp[i-1]);
	}
	rep(i,1,n)p[i].clear(),t[i]=0;//多测要清空哦！
	cout <<dp[n]<<'\n';
}

• 我会离散化！

当 $n$ 变得特别大，有用的端点也就只有 $O(m)$ 个，所以直接把 $n$ 按照任务区间的端点离散化，计算贡献依旧正常，就是要注意离散化后相邻两个值是否相差 $1$。复杂度 $O(mk\log m)$。

期望得分 $52$ 分。

这一部分代码如下：

//b 数组是离散化数组，ln 是离散化数组的长度，其它部分都一样
inline void subtask3(){
	n=ln;
	rep(i,1,m){
		a[i].l=lower_bound(b+1,b+ln+1,a[i].l)-b;
		a[i].r=lower_bound(b+1,b+ln+1,a[i].r)-b;
		p[a[i].r].pb({a[i].l,a[i].k});
	}
	rep(i,0,ln)dp[i]=0;
	rep(i,1,ln){
		E(i)add(y.first,y.second);
		for(int j=i;j>=1&&b[i]-b[j]+1<=k;j--){
			int pos=j-2;
			if(b[j-1]!=b[j]-1)pos=j-1;
			dp[i]=max(dp[i],query(j)+got(pos)-1LL*(b[i]-b[j]+1)*d);
		}
		dp[i]=max(dp[i],dp[i-1]);
	}
	cout <<dp[ln]<<'\n';
	rep(i,1,ln)t[i]=0,p[i].clear();
}

• 我会线段树！

考虑我们的复杂度始终无法摆脱一个类似 $O(n^2)$ 的瓶颈。显然在于我们每次转移都是暴力枚举左端点。而不难发现，每次枚举的左端点是一个区间，只要能够满足一个查询区间最大值的数据结构就能把复杂度降下去。但中途加入任务区间又会带来区间修改。等等，区间修改和区间最大值？这直接线段树不就行了！使用线段树来处理，每次二分最靠左的满足条件的 $j$（当然也可以双指针），复杂度 $O(m\log m)$，足以通过此题！

赛时满分代码如下（去掉文件输入输出）：

#include<bits/stdc++.h>
#define ll long long
#define mid (l+r>>1)
#define rep(x,y,z) for(int x=(y);x<=(z);x++)
#define per(x,y,z) for(int x=(y);x>=(z);x--)
#define e(x) for(int i=h[x],y=to[i];i;i=nxt[i],y=to[i])
#define Pi pair<int,int>
#define pb push_back
#define ui unsigned ll
inline int read(){int s=0,w=1;char c=getchar();while(c<48||c>57){if(c=='-')w=-1;c=getchar();}while(c>=48&&c<=57)s=(s<<1)+(s<<3)+c-'0',c=getchar();return s*w;}
const int N=2e5+5,M=1e6+5,inf=(1LL<<31)-1;
const ll llf=1e18; 
using namespace std;
int n,m,k,d,lsh[N],b[N],ln,testid,T;//days,tasks,limits,costs
struct node{
	int l,r,k;
}a[N];
inline void init(){
	ln=0;
	n=read(),m=read(),k=read(),d=read();
	lsh[m*2+1]=0;
	rep(i,1,m){
		a[i].r=read(),a[i].l=a[i].r-read()+1,a[i].k=read();
		lsh[(i<<1)-1]=a[i].l,lsh[i<<1]=a[i].r;
	}
	sort(lsh+1,lsh+m*2+1);
	rep(i,2,m*2+1)if(lsh[i]^lsh[i-1])b[++ln]=lsh[i-1];//离散化
}
ll dp[N];
inline ll got(int x){
	if(x>=0)return dp[x];
	return 0;
} 
vector<Pi >p[N];
#define E(x) for(auto y:p[x])
#define L x<<1
#define R L|1
#define lc L,l,mid
#define rc R,mid+1,r
#define OK Ll<=l&&r<=Rr
struct seg{
	ll w,laz;
}xd[N<<2];
inline void insert(int x,ll k){
	xd[x].w+=k,xd[x].laz+=k;
}
inline void pushdown(int x){
	insert(L,xd[x].laz),insert(R,xd[x].laz),xd[x].laz=0;
}
inline void getup(int x){
	xd[x].w=max(xd[L].w,xd[R].w);
}
inline void build(int x,int l,int r){
	xd[x]={0,0};
	if(l==r)return;
	build(lc),build(rc);
}
inline void modify(int x,int l,int r,int Ll,int Rr,ll k){
	if(OK)return insert(x,k),void();
	pushdown(x);
	if(Ll<=mid&&Rr>=l)modify(lc,Ll,Rr,k);
	if(Ll<=r&&Rr>mid)modify(rc,Ll,Rr,k);
	getup(x);
}
inline ll query(int x,int l,int r,int Ll,int Rr){
	if(Ll>Rr)return 0;
	if(OK)return xd[x].w;
	pushdown(x);
	if(Rr<=mid)return query(lc,Ll,Rr);
	if(Ll>mid)return query(rc,Ll,Rr);
	return max(query(lc,Ll,Rr),query(rc,Ll,Rr));
}
//线段树
#define Root 1,1,ln
inline int find(int x){
	int l=1,r=ln,ans=r;
	while(l<=r)if(b[mid]>=x)ans=mid,r=mid-1;
	else l=mid+1;
	return ans;
}//手写二分
inline void subtaskall(){
	build(Root);
	rep(i,0,ln)dp[i]=0;
	rep(i,1,m){
		a[i].l=lower_bound(b+1,b+ln+1,a[i].l)-b;
		a[i].r=lower_bound(b+1,b+ln+1,a[i].r)-b;
		p[a[i].r].pb({a[i].l,a[i].k});
	}
	rep(i,1,ln){
		E(i)modify(Root,1,y.first,y.second);
		int j=find(b[i]-k+1);
		dp[i]=max(dp[i],query(Root,j,i-1))-1LL*b[i]*d-1LL*d;
		int pos=i-2;
		if(b[i-1]!=b[i]-1)pos=i-1;
		dp[i]=max(dp[i],query(Root,i,i)+got(pos)-d);
		dp[i]=max(dp[i],dp[i-1]);
		modify(Root,i,i,got(pos)+1LL*b[i]*d);
	}
	cout <<dp[ln]<<'\n';
	rep(i,1,ln)p[i].clear();
}//dp
inline void solve(){
	subtaskall();
}
int main(){
	testid=read(),T=read();
	while(T--){
		init();
		solve();
	}
	return 0;
}

写的那么用心，点个赞再走吧 ！awa

update 2024/11/5：

• 修改了一处评论区指出的笔误。
• 一晃一年过去，又一年的 NOIP 又要开始了，如果在备战 NOIP 时感到迷茫，可以从这篇专栏获取一些建议，祝大家的 OI 生涯一帆风顺！