显然是dp啊,dp[i][j]表示到时间i打扰了j次的最小收益
显然要排序,官方题解说set没看懂,优先队列就行啊。
按照时间排序,显然这样扫的话可以保证当前时间点的点在优先队列里吧,
然后有打断和不打断两种方式。搞一下就行了。
这个题其实只要想清楚,我在每个点能选的红包是唯一的,这样子一想就变得很**了。
头脑混乱写不出来不能怪我啊,我老人家持续表演了一个月的小品了啊
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Red{
ll s,t,d,w;
bool operator<(const Red& a)const{
if(w==a.w)
return d<a.d;
return w<a.w;
}
}r[];
bool cmp(Red a,Red b){
if(a.s==b.s){
if(a.w==b.w){
return a.d>b.d;
}
return a.w>b.w;
}
return a.s<b.s;
}
int n,m,k;
ll dp[][];
priority_queue<Red> q;
int main() {
ios::sync_with_stdio(false);
cin>>n>>m>>k;
for(int i=;i<=n+;i++)for(int j=;j<=m;j++)dp[i][j]=1e18;
for(int i=;i<=k;i++){
cin>>r[i].s>>r[i].t>>r[i].d>>r[i].w;
}
sort(r+,r++k,cmp);
int j=;
for(int i=;i<=n;i++){//
for(;j<=k;){
if(r[j].s<=i) {
q.push(r[j]);
j++;
} else break;
}
while (!q.empty()&&q.top().t<i) q.pop();
if(q.empty()){
for(int l=;l<=m;l++){
dp[i+][l]=min(dp[i+][l],dp[i][l]);
}
continue;
}
Red tmp = q.top();
for(int l=;l<=m;l++) {
dp[min(tmp.d+,n+1ll)][l]=min(dp[min(tmp.d+,n+1ll)][l],dp[i][l]+tmp.w);
}
for(int l=;l<=m;l++){
dp[i+][l]=min(dp[i+][l],dp[i][l-]);
}
}
ll ans = 1e18;
for(int i=;i<=m;i++){
ans = min(ans,dp[n+][i]);
}
cout<<ans<<endl;
}