P9871 天天爱打卡

· · 题解

暴力转移

定义 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 
//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 对当前决策点的影响：

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

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

#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;
}