题解：P12247 跳舞机

· · 题解

题目分析

考虑 DP。设计状态 dp_i 表示前 i 分钟能获得的最大兴奋值之和，定义 maxn_i 为某个玩家玩一局从 i - k + 1 分钟到 i 分钟的游戏所能获得的最大兴奋值（其实就是所有停留时间包含 [i - k + 1 , i] 的玩家当中最大的 w）。那么有状态转移方程

dp_i = \max(dp_{i-1} , dp_{i - k} + maxn_i)

现在考虑如何计算 maxn_i。注意到对于某个玩家 i，其停留时间 [l_i , r_i] 包含的所有长度等于 k 的区间都可以作为一局，这些区间能获得的最大值都应该被更新为与 w_i 取最大值。而这些区间就是所有的右端点在区间 [l_i + k - 1 , r_i] 的长度为 k 的区间（可能说的比较绕，自己理解一下即可），所以可以对于所有的 l_i + k - 1 \le j \le r_i，更新 maxn_j = \max(maxn_j,w_i)。这怎么实现呢？用线段树是显然可以的，但考虑到离线，其实完全没有必要用线段树，毕竟“杀鸡焉用牛刀”。我们可以使用堆来实现，但更简单的方法是用 STL 中的 multiset。如果是区间加，我们会用差分。而我们要区间对同一数取最大值，于是想到借鉴差分的思路，在 l_i + k - 1 处开一个 vector 名为 add，加入 w_i，表示处理到这里的时候往 multiset 中加入 w_i；在 r_i + 1 处开一个 vector 名为 del，加入 w_i，表示处理到这里的时候删除 multiset 中的一个 w_i。然后利用 multiset 的自动排序特性，直接取出其中的最后一个数，就得到到了 maxn_j。

时间复杂度瓶颈在于 multiset 的操作，时间复杂度为 O(n \log n)。

参考代码

#include<iostream>
#include<vector>
#include<set>
#define int long long
using namespace std;
int n,m,k;
int l[(int)5e5+5],r[(int)5e5+5],w[(int)5e5+5];
vector<int> add[(int)5e5+5],del[(int)5e5+5];
multiset<int> s;
int dp[(int)5e5+5];
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++) cin>>l[i]>>r[i]>>w[i];
    for(int i=1;i<=n;i++){
        if(l[i]+k-1<=r[i]){
            add[l[i]+k-1].push_back(w[i]);
            del[r[i]+1].push_back(w[i]);
        }
    }
    for(int i=1;i<=m;i++){
        for(int j=0;j<add[i].size();j++) s.insert(add[i][j]);
        for(int j=0;j<del[i].size();j++) s.erase(s.find(del[i][j]));
        dp[i]=dp[i-1];
        if(i>=k&&!s.empty()) dp[i]=max(dp[i],dp[i-k]+*prev(s.end()));
    }
    cout<<dp[m];
    return 0;
}