#C241004B. 方差
标签（Label）
- 动态规划
网址（Website）
题目（Problem）
详情如下
题目描述
现在有 $n$ 个区间 $[l_i, r_i]$，每个区间有个权值 $w_i$。 我们把这 $n$ 个区间当成 $n$ 个点，如果两个区间它们之间有交（包括端点），那么我们就在这两个区间之间连边，形成了一个区间图。
现在希望你删除一些区间，使得每个连通块大小不超过 $k$。
输出删除区间最小的权值和。
输入格式
从文件 variance.in 中读入数据。
第一行两个整数 $n, k$。
接下来 $n$ 行，每行三个整数 $l_i, r_i, w_i$。
输出格式
输出到文件 variance.out 中。
输出一个整数，表示答案。
样例
输入数据 1
5 2
1 4 1
3 6 2
5 8 5
7 10 2
9 12 1输出数据 1
3【输入输出样例2】
见选手目录下的 variance/variance2.in 与 variance/variance2.ans。
数据规模与约定
一共 10 个测试点。
对于测试点 1,2，保证 $n \leq 20$。
对于测试点 3,4，保证 $n \leq 100$。
对于测试点 5,6，保证 $n \leq 500$。
对于所有测试点，保证 $1 \leq k \leq n \leq 2500$；$1 \leq l_i \leq r_i \leq 10^9$；$1 \leq w_i \leq 10^9$。
题解（Solution）
$\qquad$根据连边的方式分析，如果要分开一个连通块，一定要把包含某个点的所有区间。
$\qquad$我们令 $f[i]$ 表示从 $1$ 到 $2n$ （离散化后最多 $2n$ 个点）枚举，当前枚举到 $i$ ，此时能取得的最大的贡献，将所有区间按右端点排序，如果 $i$ 到了右端点就加入区间，向前枚举 $j$ ，表示上一个删除的点，很容易处理出中间的区间有哪些，用一个优先队列，每次只取权值前 $k$ 大的区间保留，其他的删除，最后用总权值减去 $f[2n]$ 即可。
$\qquad$时间复杂度 $O(n^2\log n)$ 。
出题者题解
算法分析
可以发现，最后肯定是删除经过某些位置的所有区间。
记 $dp[i]$，表示当前切到 $i$ 这个位置，然后枚举上一段切什么地方 $j$，然后考虑 $[i,j]$ 之间的区间只保留价值最大的 $k$ 个，把其他的都删了，这样直接做是 $O(n^3 \log n)$ 的。从后往前枚举 $j$，依次加入区间，然后用堆维护一下前 $k$ 大即可，时间复杂度 $O(n^2 \log n)$，但是实际很快。
代码（Code）
#include<bits/stdc++.h>
#include<vector>
#include<queue>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int>
#define int long long
#define x first
#define y second
inline int rd(){int x;return cin>>x,x;}
const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 201234;
bool ST;
int a[N],b[N],v[N];
int c[N],f[N];
int n,m,s,tot=0;
priority_queue<int> q;
vector<P> g[N];
vector<int> h[N];
inline void solve(){
n = rd(), m = rd();
For(i,1,n){
cin>>a[i]>>b[i]>>v[i];
s+=v[i];//记录权值总和
c[++tot]=a[i],c[++tot]=b[i];//
}sort(c+1,c+tot+1);
For(i,1,n){
a[i] = lower_bound(c+1,c+tot+1,a[i])-c;
b[i] = lower_bound(c+1,c+tot+1,b[i])-c;
g[b[i]].emplace_back(a[i],v[i]);//记录区间，定右端点
}
For(i,1,n*2){//离散化后最多有2n个点
for(auto p:g[i]) h[p.x].emplace_back(p.y);//左端点的贡献
int sum = 0, t = 0;
while(q.size()) q.pop();
Rof(j,i,1){
for(auto k:h[j]){//枚举区间
if(++t<=m) q.emplace(-k),sum+=k;//如果没超过了k个
else if(-q.top()<k){//否则将贡献小的弹出
sum+=q.top();
sum+=k;
q.pop();
q.emplace(-k);
}f[i] = max(f[i], f[j-1]+sum);
}
}
}cout<<s-f[2*n]<<'\n';
}
bool ED;
signed main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
// freopen("ex_variance2.in","r",stdin);
freopen("variance.in","r",stdin);
freopen("variance.out","w",stdout);
int T = 1, Tim = clock();
while(T--) solve();
return cerr<<"TIME:"<<(clock()-Tim)/1000.,0;
} 
