题解：P11239 「KTSC 2024 R2」跳跃游戏

Zaunese · 2025-01-11 11:39:20 · 题解

考虑 O(N) 怎么做。

转化成选若干个点，任意点间距离至少为 K，点权和最大。

考虑 DP：考虑了 0\sim i，点权和最大为 f(i)，有单步转移 f(i)=\max(f(i-1),f(i-K)+A_i)。\max 的左右两边分别表示选或不选 A_i。初值 f(0)=A_0。

考虑优化转移。

如果只考虑“选”，可以考虑把模 K 相同的 i 放到数列的同一位置上（即原地化），一次转移只要给所有位置加上对应的 A_i。这可以用离散化、线段树轻松完成。

考虑“不选”。感觉不是很好做，于是变单步转移为断点转移。具体地，改写 f(i) 的定义为考虑到了前 i 个点，其中第 i 个必须选。转移为 f(i)=\max_{0\le j\le i-K}\{f(j)\}+A_i。

延续模 K 分类、除 K 分层的思路。向 f(i) 转移的过程可以表示为下图。

圆圈表示 f(i)，红线部分是 \{f(j)\}_{0\le j\le i-K}。

具体地，要转移的就是上上层及以前的全局 \max，和上层的前缀 \max，更新到 f(i)。

一整层转移完 \max 后，给所有位置加上对应的 A_i。

可以轻松地发现，离散化之后，只要在每个 A_i 区间的左端点处存 DP 值，否则答案上可能不优。

直接做大约是 O(\frac NK) 的，这是因为有的区间可能太长，此时转移方程中的 \max 必然取 f(i-K)，只要算一下 A_i 加了多少次就行了。

时间复杂度 O(Q\log Q)。

大概是一份 QOJ 上可过的代码。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include"jumpgame.h"
#include<tuple>

#define fi first
#define se second
#define mkp std::make_pair
using ll=long long;
using std::min;
using std::max;
template<class T> void cmax(T&a,T b){a=max(a,b);}
template<class T> void cmin(T&a,T b){a=min(a,b);}

ll play_game(ll N, int Q, ll K, std::vector<ll> L, std::vector<ll> R){
    const ll INF=ll(1e18)+100;

    std::vector<ll> tad(Q*4+5),trs(Q*4+5);
    std::vector<ll> dic;
    auto doadd=[&](int x,ll z){
        trs[x]+=z;
        tad[x]+=z;
    };
    auto dn=[&](int x){
        if(tad[x]){
            doadd(x*2,tad[x]);
            doadd(x*2+1,tad[x]);
            tad[x]=0;
        }
    };
    auto add=[&](auto&&self,int x,int l,int r,ll ql,ll qr,ll z)->void{
        if(qr<dic[l]||dic[r]<ql) return;
        if(ql<=dic[l]&&dic[r]<=qr) doadd(x,z);
        else{
            int mid=l+r>>1;
            dn(x);
            self(self,x*2,l,mid,ql,qr,z);
            self(self,x*2+1,mid+1,r,ql,qr,z);
            trs[x]=max(trs[x*2],trs[x*2+1]);
        }
    };
    auto upd=[&](auto&&self,int x,int l,int r,ll p,ll z)->void{
        if(p<dic[l]||dic[r]<p) return;
        if(l==r) cmax(trs[x],z);
        else{
            int mid=l+r>>1;
            dn(x);
            self(self,x*2,l,mid,p,z);
            self(self,x*2+1,mid+1,r,p,z);
            trs[x]=max(trs[x*2],trs[x*2+1]);
        }
    };
    auto que=[&](auto&&self,int x,int l,int r,ll ql,ll qr)->ll{
        if(qr<dic[l]||dic[r]<ql) return 0;
        if(ql<=dic[l]&&dic[r]<=qr) return trs[x];
        else{
            int mid=l+r>>1;
            dn(x);
            return max(self(self,x*2,l,mid,ql,qr),
                    self(self,x*2+1,mid+1,r,ql,qr));
        }
    };
    auto build=[&](auto&&self,int x,int l,int r)->void{
        if(l==r){
            trs[x]=l?-INF:0;
        }else{
            int mid=l+r>>1;
            self(self,x*2,l,mid);
            self(self,x*2+1,mid+1,r);
            trs[x]=max(trs[x*2],trs[x*2+1]);
        }
    };
    auto dfs=[&](auto&&self,int x,int l,int r)->void{
        printf("%d[%d,%d]%lld\n",x,l,r,trs[x]);
        if(l!=r){
            int mid=l+r>>1;
            dn(x);
            self(self,x*2,l,mid);
            self(self,x*2+1,mid+1,r);
        }
    };

    std::vector<std::pair<ll,int> > v;
    dic.push_back(-1);
    for(int i=0;i<Q;++i){
        dic.push_back(L[i]%K);
        v.emplace_back(L[i],1);
        v.emplace_back(R[i]+1,-1);
    }
    std::sort(dic.begin(),dic.end());
    dic.erase(std::unique(dic.begin(),dic.end()),dic.end());
    build(build,1,0,dic.size()-1);
    std::sort(v.begin(),v.end());
    ll sum=0,last=-1;
    for(int i=0;i<(int)v.size();){
        ll b=v[i].fi/K;
        if(b-last>1){
            upd(upd,1,0,dic.size()-1,-1,trs[1]+(b-last-2)*sum);
            add(add,1,0,dic.size()-1,0,K,(b-last-1)*sum);
        }
        ll l=0,x=trs[1];
        int j=i;
        std::vector<std::tuple<ll,ll,ll> > upds;
        for(;j<(int)v.size()&&v[j].fi/K==b;++j){
            upds.emplace_back(l,v[j].fi%K-1,sum);
            if(v[j].se>0){
                upd(upd,1,0,dic.size()-1,v[j].fi%K,
                        que(que,1,0,dic.size()-1,-1,v[j].fi%K));
            }
            sum+=v[j].se;
            l=v[j].fi%K;
        }
        upds.emplace_back(l,K-1,sum);
        upd(upd,1,0,dic.size()-1,-1,x);
        last=v[i].fi/K;
        for(auto p:upds){
            ll l,r,x;
            std::tie(l,r,x)=p;
            add(add,1,0,dic.size()-1,l,r,x);
        }
        i=j;
    }
    fprintf(stderr,"%d\n",1);
    return trs[1];
}