题解：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 记录。

代码

CPP

#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;
}

题解：P12247 跳舞机

文章操作

跳舞机

题目大意

解析

代码

相关推荐

评论

题解：P12247 跳舞机