暴力转移

定义

f_i

表示第

i

天强制跑步，前

i

天最多能拿到的能量。

枚举本次跑步的起点 $j$ ，则

[j,i]

跑步，获得的能量是

[l,r]\in[j,i]

的挑战。

上一次跑步的起点可以是

[1,j-2]

的任意一个点，也可以是

0

表示一开始不跑步。

所以再设一个

g[i]=\max_{j=1}^{i-1}{f_j}

，则

f[i]=\max_{j=i-k+1}^{i}g[j-2]-(i-j+1)\times d+\sum val

CPP

//28pts 暴力
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+7;
int idx,T,n,m,k,d,dp[N],f[N];
struct NODE{
	int len,val;
};
vector<NODE> a[N];
signed main(){
//	freopen("run.in","r",stdin);
//	freopen("run.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>idx>>T;
	while(T--){
		cin>>n>>m>>k>>d;
		memset(dp,0,sizeof dp);
		memset(f,0,sizeof f);
		for(int i=1;i<=n;i++) a[i].clear();
		for(int i=1;i<=m;i++){
			int x,y,z;
			cin>>x>>y>>z;
			NODE res={y,z};
			a[x].push_back(res);
		}
		for(int i=1;i<=n;i++){
			for(int j=i;j>=max(0ll,i-k+1ll);j--){
				int w=0;
				for(int x=j;x<=i;x++){
					for(auto y:a[x]){
						if(y.len<=(x-j+1)){
							w+=y.val;
						}
					}
				}
				dp[i]=max(dp[i],f[j-2]-(i-j+1)*d+w);
			}
			f[i]=max(f[i-1],dp[i]);
		}
		cout<<f[n]<<'\n';
	}
	return 0;
}

正解

用线段树下标表示决策点，对应的值表示决策值，这样就可以直接：

f[i]=query(1,i-k+1,i)

了。

观察如何

i\to i+1

对当前决策点的影响：

首先 $[0,i-1]$ 区间全部减去 $d$ 的贡献。
一个 $[l,r]$ 且 $r=i$ 的挑战在此刻插入线段树中。因为线段树维护的是跑步起点 $j$ 。所以对于所有在 $[0,l]$ 的点，其实开始一直跑的话都是会得到贡献的。所以插入。
$g[j-2]$ ，发现 $g$ 的值会作用在两个位置之后。所以插入到两个位置后即可。

然后进行离散化。但实现细节有点恶心……只能看代码理解咯？

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+7;
int idx,T,n,m,k,d,f[N];
struct NODE{
	int l,r,val;
}a[N];
bool cmp(NODE a1,NODE a2){
	return a1.r<a2.r;
}
struct TREE{
	int l,r,mx,tag;
}tr[N<<2];
void push_up(int p){
	tr[p].mx=max(tr[p<<1].mx,tr[p<<1|1].mx);
}
void build(int p,int l,int r){
	tr[p]={l,r,0,0};
	if(l==r) return;
	int mid=(l+r)>>1;
	build(p<<1,l,mid);
	build(p<<1|1,mid+1,r);
	push_up(p);
}
void push_down(int p){
	if(tr[p].tag==0) return;
	tr[p<<1].tag+=tr[p].tag, tr[p<<1].mx+=tr[p].tag;
	tr[p<<1|1].tag+=tr[p].tag, tr[p<<1|1].mx+=tr[p].tag;
	tr[p].tag=0;
}
void update(int p,int l,int r,int x){
	if(l<=tr[p].l&&tr[p].r<=r){
		tr[p].mx+=x, tr[p].tag+=x;
		return;
	}
	int mid=(tr[p].l+tr[p].r)>>1;
	push_down(p);
	if(l<=mid) update(p<<1,l,r,x);
	if(mid<r) update(p<<1|1,l,r,x);
	push_up(p);
}
int query(int p,int l,int r){
	if(l>r) return 0; 
	if(l<=tr[p].l && tr[p].r<=r){
		return tr[p].mx;
	}
	int mid=(tr[p].l+tr[p].r)>>1,res=-114514;
	push_down(p);
	if(l<=mid) res=max(res,query(p<<1,l,r));
	if(mid<r) res=max(res,query(p<<1|1,l,r));
	return res;
}
int t[N],cnt;
int getid(int x){
	return lower_bound(t+1,t+1+cnt,x)-t;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>idx>>T;
	while(T--){
		cin>>n>>m>>k>>d; cnt=0;
		memset(f,0,sizeof f);
		for(int i=1;i<=m;i++){
			int x,y,z;
			cin>>x>>y>>z;
			a[i]={x-y,x,z};
			t[++cnt]=x-y;
			t[++cnt]=x;
		}
		sort(t+1,t+1+cnt);
		cnt=unique(t+1,t+1+cnt)-t-1;
		build(1,0,cnt+10);
		for(int i=1;i<=m;i++){
			a[i].l=getid(a[i].l);
			a[i].r=getid(a[i].r);
		}
		sort(a+1,a+1+m,cmp);
		int res=0,p=1;
		//tr[x] 查找到的是本次跑步的起点的前一个点 
		for(int i=1;i<=cnt;i++){//第 i 个关键位置 
			update(1,0,i-1,-d*(t[i]-t[i-1]));
			while(p<=m && a[p].r==i){
				update(1,0,a[p].l, a[p].val);
				p++;
			}
			res=max(res,query(1,getid(t[i]-k),i-1));
			update(1,i+1,i+1,res);
		}
		cout<<res<<'\n';
	}
	return 0;
}

P9871 天天爱打卡

文章操作

暴力转移

正解

相关推荐

评论

P9871 天天爱打卡