题解：P12247 跳舞机

· · 题解

跳舞机

题目大意

小 O 有一台跳舞机， n 个人在 m 分钟内游玩，每个人在 L_{i} 到 R_{i} 的时间内游玩，跳舞时间固定为 k 。

解析

显然在同一时间段 i-k+1 到 i 内每个人只有在场与不在场两种情况，我们可以贪心的选择能玩中兴奋值 w 最大的人跳舞(下文用 \operatorname{ w_{i-k+1} } 表示)。

对于不同时间段的选择可以想到 DP ，我们可以设 \operatorname{DP_{i}} 是在第 i 分钟内取得的最大兴奋值，可以在第 i 分钟内可以选择不跳舞，也可以在第 i-k+1 分钟到第 i 分钟内跳舞， DP 方程就得出了：

\operatorname{DP_{i}}= \max(\operatorname{DP_{i-1}},\operatorname{DP_{i-k}}+\operatorname{w_{i-k+1}})

不难发现一个人只有在 L_{i} 到 R_{i}-k+1 分钟才有可能开始跳舞，于是可以求出从 i 分钟开始的最大兴奋值 w_{i} ,但一个一个找肯会 TLE ，我们可以用线段树来完成区间修改，单点查询。最终时间复杂度为 O((n+m)\log m) 。

AC 记录。

代码


#include <bits/stdc++.h>
using namespace std;

const int N=5e5+10;

struct player{int l,r,w;};
struct linetree{int l,r,val;};

int n,m,k;

long long dp[N];//DP数组
player f[N];
linetree tr[N<<2];//线段树

void pushdown(int u){//把父节点的值传给子代
    tr[u<<1].val=max(tr[u<<1].val,tr[u].val);
    tr[u<<1|1].val=max(tr[u<<1|1].val,tr[u].val);
}

void build(int u,int l,int r){//建树
    tr[u].l=l,tr[u].r=r;
    if(l!=r){
        int mid=l+r>>1;
        build(u<<1,l,mid),build(u<<1|1,mid+1,r);
    }
}

void add(int u,int l,int r,int val){//区间修改最大值
    if(l<=tr[u].l && tr[u].r<=r){
        tr[u].val=max(tr[u].val,val);
        return;
    }
    int mid=tr[u].l+tr[u].r>>1;
    if(l<=mid)add(u<<1,l,r,val);
    if(r>mid)add(u<<1|1,l,r,val);
}

int query(int u,int x){//单点查询
    if(tr[u].l==tr[u].r){
        return tr[u].val;
    }
    pushdown(u);
    int mid=tr[u].l+tr[u].r>>1;
    if(x<=mid)return query(u<<1,x);
    else return query(u<<1|1,x);
}

int main(){
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
  //输入
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++){
        cin>>f[i].l>>f[i].r>>f[i].w;
    }

  //建树，预处理最大值
    build(1,1,m);
    for(int i=1;i<=n;i++){
        if(f[i].r+1-tr[i].l>=k){
            add(1,f[i].l,f[i].r+1-k,f[i].w);
        }
    }
  //dp求值
    for(int i=k;i<=m;i++){
        dp[i]=max(dp[i-1],dp[i-k]+query(1,i-k+1));
    }

    cout<<dp[m];
    return 0;
}