题解：P12247 跳舞机

未来姚班zyl · 2025-04-19 19:22:53 · 题解

• 注：本题虽然正解形式简单，代码简短，但对于普及组选手，需要一定的思维能力和经验积累才能做出此题，且对于思考的过程，带有许多合适的部分分。

考察贪心、简单动态规划、stl 库的数据结构应用。

考虑设 dp_i 表示前 i 分钟的答案。那么对于所有可以在 [i-k+1,i] 期间玩一次跳舞机的玩家，他们的 l 与 r 与当前决策无关，所以取最大的 w 一定最优，设这个最大的 w 为 W_i，则 dp_i=\max(dp_{i-1},dp_{i-k}+W_i)。

考虑求出所有 W_i。枚举玩家 i，显然其对 j\in [l_i+k-1,r_i] 的 W_j 有贡献。

问题转换为，有 n 个数，每个数覆盖了一个区间，求每个位置的数的最大值。

我们考虑维护一个可重集 S，从 1 扫到 m，对于每个数 w 和其覆盖的区间 [l,r]，在 l 时将 w 加入 S，在 r+1 时将 w 移出 S，同时支持查询 S 中的最大值，使用 std::map 或者 std::multiset 维护即可。

如果没想到正解，可以得到贪心的部分分或者不包含数据结构的部分分。

#include<bits/stdc++.h>
#define ll long long
#define rep(x,y,z) for(int x=(y);x<=(z);x++)
#define per(x,y,z) for(int x=(y);x>=(z);x--)
#define repn(x) rep(x,1,n)
#define repm(x) rep(x,1,m)
#define pb push_back
inline int read(){int s=0,w=1;char c=getchar();while(c<48||c>57) {if(c=='-') w=-1;c=getchar();}while(c>=48&&c<=57)s=(s<<1)+(s<<3)+c-48,c=getchar();return s*w;}
inline void pf(ll x){if(x<0) putchar('-'),x=-x;if(x>9)pf(x/10);putchar(x%10+48);}
using namespace std;
const int N=5e5+5;
int n,m,k;
ll dp[N];
struct node{
    int k,ty;
};
vector<node>p[N];
map<int,int>P;
inline void Main(){
    n=read(),m=read(),k=read();
    repn(i){
        int l=read()+k-1,r=read(),w=read();
        if(l<=r)p[l].pb({w,1}),p[r+1].pb({w,-1});
    }
    repm(i){
        for(auto y:p[i])if(y.ty==1)P[y.k]++;
        else {
            if(P[y.k]==1)P.erase(y.k);
            else P[y.k]--;
        }
        dp[i]=dp[i-1];
        if(!P.empty())dp[i]=max(dp[i],dp[i-k]+(*--P.end()).first);
    }
    cout <<dp[m];
}
signed main(){
    int T=1;
    while(T--)Main();
    return 0;
}