P9871题解
operator_
·
·
题解
P9871 [NOIP2023] 天天爱打卡
题目传送门
题解
T4 天天爱打卡(run)
考察：dp、线段树
先考虑 n=10^5 的部分分。动态规划是显然的：记 f_{i,0/1} 表示前 i 位，最后一位选/不选的最大能量。转移： f_{i,0}=\max(f_{i-1,0},f_{i-1,1})，f_{i,1}=\max_{i-j+1\le k}(f_{j-1,0}+val(j,i))。也是显然的线段树优化，把 val 拆成加减两部分，减的部分是简单的，而加的部分对挑战按结束时间排序，然后指针扫描即可。
接下来考虑满分做法，基于一个贪心理念：跑步的目的是为了完成挑战，所以显然就是对所有挑战的起始与终止点进行离散化，但是转移就有点不同了。
记 f_{i,0/1} 表示前 i 个关键点，最后一个选/不选的最大能量。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read() {
int s=0,m=0;char ch=getchar();
while(!isdigit(ch)) {if(ch=='-')m=1;ch=getchar();}
while( isdigit(ch)) s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
return m?-s:s;
}
#define inf ((int)1e12)
int c,t,n,m,k,d,b[200005],cnt,f[200005][2];
struct QWQ {int l,r,v;} a[100005];
bool cmp(QWQ a1,QWQ a2) {return a1.r<a2.r;}
struct Node {int l,r,d,laz;};
struct Segment_Tree {
Node t[4*200005];
int ls(int p) {return p<<1;}
int rs(int p) {return p<<1|1;}
void pushup(int p) {t[p].d=max(t[ls(p)].d,t[rs(p)].d);}
void pushdown(int p) {
t[ls(p)].d+=t[p].laz,t[rs(p)].d+=t[p].laz;
t[ls(p)].laz+=t[p].laz,t[rs(p)].laz+=t[p].laz;t[p].laz=0;
}
void clear(int p,int l,int r) {
t[p].l=l,t[p].r=r,t[p].d=-inf,t[p].laz=0;
if(l==r) return;int m=(l+r)>>1;
clear(ls(p),l,m);clear(rs(p),m+1,r);
}
void update(int p,int l,int r,int v) {
if(l>r) return;
if(l<=t[p].l&&t[p].r<=r) {t[p].d+=v,t[p].laz+=v;return;}
pushdown(p);int m=(t[p].l+t[p].r)>>1;
if(l<=m) update(ls(p),l,r,v);
if(r>m) update(rs(p),l,r,v);pushup(p);
}
int query(int p,int l,int r) {
if(l<=t[p].l&&t[p].r<=r) return t[p].d;
pushdown(p);int s=-inf,m=(t[p].l+t[p].r)>>1;
if(l<=m) s=max(s,query(ls(p),l,r));
if(r>m) s=max(s,query(rs(p),l,r));return s;
}
} tt;
signed main() {
cin>>c>>t;
while(t--) {
cin>>n>>m>>k>>d;
b[cnt=1]=n;
for(int i=1;i<=m;i++) {
int x=read(),y=read();
b[++cnt]=a[i].l=x-y+1,b[++cnt]=a[i].r=x,a[i].v=read();
}
sort(b+1,b+cnt+1);int q=unique(b+1,b+cnt+1)-b-1;
tt.clear(1,1,200002);
memset(f,-0x3f,sizeof(f));f[0][0]=0;tt.update(1,1,1,inf);
for(int i=1;i<=m;i++)
a[i].l=lower_bound(b+1,b+q+1,a[i].l)-b,a[i].r=lower_bound(b+1,b+q+1,a[i].r)-b;
sort(a+1,a+m+1,cmp);
for(int i=1,j=1,r=1;i<=q;i++) {
tt.update(1,1,i-1,-d*(b[i]-b[i-1]));
while(b[i]-b[j]+1>k) j++;
while(r<=m&&a[r].r==i)
tt.update(1,1,a[r].l,a[r].v),r++;
f[i][0]=max(max(f[i-1][0],f[i-1][1]),0ll);
f[i][1]=tt.query(1,j,i)-d;
if(b[i+1]-b[i]==1) tt.update(1,i+1,i+1,inf+f[i][0]);
else tt.update(1,i+1,i+1,inf+max(f[i][0],f[i][1]));
}
printf("%lld\n",max(f[q][0],f[q][1]));
}
return 0;
}
```
时间复杂度 $O(m\log m)$。