小清新 DP 题。
定义 \(f_{i,j}\) 表示在时刻 \(i\)，干扰了 \(j\) 次，最小贡献。
定义 \(nex_i\) 表示在时刻 \(i\) 会收集哪个红包。
那么转移方程为：
\[f_{d_{nex_i}+1,j}=\min(f_{i,j}+w_{nex_i})
\]
\[f_{i+1,j+1}=\min(f_{i,j})
\]
其中，\(f_{1,0}=0\)，\(ans=\min\limits_{j=0}^{m}f_{n+1,j}\)。\(d_{nex_i}+1\) 为选完编号为 \(w_{nex_i}\) 的红包后会跳到那个位置。
现在考虑如何预处理出 \(nex_i\)。
可以先以 \(w\) 为第一关键字，\(d\) 为第二关键字从大到小排序。
然后将区间 \([s,t]\) 中的 \(nex\) 全部标记为当前编号，之后不再访问。
这里可以用并查集维护已经访问过的区间，遇到访问过的直接查询并查集跳过去即可。
复杂度 \(O(nm+n\log n)\)。
code:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e5+5,N2=200+5,inf=LLONG_MAX>>1;
int n,m,k,vis[N],nex[N],fa[N];
ll f[N][N2];
struct node{int s,t,d;ll w;}a[N];
bool cmp(node x,node y){return x.w!=y.w?x.w>y.w:x.d>y.d;}
int ff(int x){return fa[x]==x?x:fa[x]=ff(fa[x]);}
int main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n>>m>>k;
for(int i=1;i<=k;++i)cin>>a[i].s>>a[i].t>>a[i].d>>a[i].w;
sort(a+1,a+k+1,cmp);
for(int i=1;i<=n+1;++i)fa[i]=i;
for(int i=1;i<=k;++i){
int j=a[i].s;
while(j<=a[i].t){
if(vis[j])j=ff(j);
else {
vis[j]=1;
nex[j]=i;
fa[ff(j)]=ff(j+1);
++j;
}
}
}
for(int i=1;i<=n+1;++i)for(int j=0;j<=m;++j)f[i][j]=inf;
f[1][0]=0;
for(int i=1;i<=n;++i){
for(int j=0;j<=m;++j){
f[i+1][j+1]=min(f[i+1][j+1],f[i][j]);
if(nex[i])f[a[nex[i]].d+1][j]=min(f[a[nex[i]].d+1][j],f[i][j]+a[nex[i]].w);
else f[i+1][j]=min(f[i+1][j],f[i][j]);
}
}
ll ans=inf;
for(int j=0;j<=m;++j)ans=min(ans,f[n+1][j]);
cout<<ans<<endl;
return 0;
}