专栏文章

题解：P12247 跳舞机

未未来姚班zyleternal love
P12247题解参与者 6已保存评论 5

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
5 条
当前快照
1 份
快照标识符
@mipk41z2
此快照首次捕获于
2025/12/03 13:18
3 个月前
此快照最后确认于
2025/12/03 13:18
3 个月前
查看原文
  • 注：本题虽然正解形式简单，代码简短，但对于普及组选手，需要一定的思维能力和经验积累才能做出此题，且对于思考的过程，带有许多合适的部分分。
考察贪心、简单动态规划、stl 库的数据结构应用。
考虑设 dpidp_i 表示前 ii 分钟的答案。那么对于所有可以在 [i−k+1,i][i-k+1,i] 期间玩一次跳舞机的玩家，他们的 ll 与 rr 与当前决策无关，所以取最大的 ww 一定最优，设这个最大的 ww 为 WiW_i，则 dpi=max⁡(dpi−1,dpi−k+Wi)dp_i=\max(dp_{i-1},dp_{i-k}+W_i)。
考虑求出所有 WiW_i。枚举玩家 ii，显然其对 j∈[li+k−1,ri]j\in [l_i+k-1,r_i] 的 WjW_j 有贡献。
问题转换为，有 nn 个数，每个数覆盖了一个区间，求每个位置的数的最大值。
我们考虑维护一个可重集 SS，从 11 扫到 mm，对于每个数 ww 和其覆盖的区间 [l,r][l,r]，在 ll 时将 ww 加入 SS，在 r+1r+1 时将 ww 移出 SS，同时支持查询 SS 中的最大值，使用 std::map 或者 std::multiset 维护即可。
如果没想到正解，可以得到贪心的部分分或者不包含数据结构的部分分。
CPP
#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;
}

评论

共 5 条评论，欢迎与作者交流。

正在加载评论...