layout: post
title: Codeforces Round 536 (Div. 2)
author: "luowentaoaa"
catalog: true
tags:
mathjax: true
- codeforces
- DP
- 数据结构
前四题签到题不讲，
E.Lunar New Year and Red Envelopes (DP+数据结构)
题意
有k个红包，每个红包可以在一个时间段拿起，并且在拿起之后知道D时间都不能拿其他红包
如果在某一时刻可以拿红包会拿金额最大的，如果金额同样大会拿D最大的，
有m次干扰的机会，可以让在某一时刻不能拿红包。
问最少可以得到多少金额
题意
首先，每一时刻拿哪个红包和时间D都已经固定了，于是我们就直接构造dp转移一下就行
\[dp[i][j]=在i时刻用了j次机会得到的最少金额
\]
\]
那么对于一个时刻，如果没有红包那么就直接转移到下一时间
\[dp[i+1][j]=min(dp[i+1][j]，dp[i][j]);
\]
\]
如果可以抢红包那么，
\[dp[i+1][j+1]=min(dp[i+1][j+1],dp[i][j]) 被打扰
\]
\]
\[dp[d+1][j]=min(dp[d+1][j],dp[i][j]+w[i]);//不去打扰；dp[d+1][j]=min(dp[d+1][j],dp[i][j]+w[i]);//不去打扰
\]
\]
然后这题的很多解法的DP都差不多,主要差别是如何获取每一时间的最优金额和D的，
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e5+20;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
ll dp[maxn][205];
int n,m,k;
struct node{
int w,d;
void add(int ww,int dd){
if(ww>w)w=ww,d=dd;
if(ww==w&&dd>d)d=dd;
}
}my[maxn<<2];
void down(int i){
my[i<<1].add(my[i].w,my[i].d);
my[i<<1|1].add(my[i].w,my[i].d);
}
void update(int i,int l,int r,int ql,int qr,int w,int d){
if(l>=ql&&r<=qr){
my[i].add(w,d);
return;
}
int mid=(l+r)/2;
down(i);
if(ql<=mid)update(i<<1,l,mid,ql,qr,w,d);
if(qr>mid)update(i<<1|1,mid+1,r,ql,qr,w,d);
}
node query(int i,int l,int r,int pos){
if(l==r){
return my[i];
}
down(i);
int mid=(l+r)/2;
if(pos<=mid)query(i<<1,l,mid,pos);
else query(i<<1|1,mid+1,r,pos);
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
cin>>n>>m>>k;
for(int i=1;i<=k;i++){
int s,t,d,w;
cin>>s>>t>>d>>w;
update(1,1,n,s,t,w,d);
}
memset(dp,inf,sizeof(dp));
for(int i=0;i<=m;i++)dp[1][i]=0;
for(int i=1;i<=n;i++){
node now=query(1,1,n,i);
int w=now.w;int d=now.d;
for(int j=0;j<=m;j++){
if(d){
dp[d+1][j]=min(dp[d+1][j],dp[i][j]+w);
dp[i+1][j+1]=min(dp[i+1][j+1],dp[i][j]);
}
else
dp[i+1][j]=min(dp[i+1][j],dp[i][j]);
}
}
ll ans=inf;
for(int i=0;i<=m;i++)ans=min(ans,dp[n+1][i]);
cout<<ans<<endl;
return 0;
}