CF1106

记录：10月25日 10点58分 核弹发明了最小斯坦纳树！！！

废话

1. 核弹好巨
2. 核弹好巨好巨
3. 核弹好巨好巨好巨
   ……

n. 核弹好巨 …… (n-2) …… 好巨

正文

A

扫一遍即可

B

直接按题意模拟即可

C

因为他是一个和的平方的和，所以我们要选最少的数，让和尽量接近平均值
所以我们每次选两个数，分别是当前最大和当前最小

D

字典序？ 贪心！！！

每次都选他的儿子中字典序最小的
可以发现这个把 dij 改改就行了

E

可以发现，你选完一个点后，他会直接跳出这个点的可选区间，于是每个点能选的就是固定的
预处理！！！

struct node{
	int s,t,d,w;
	bool operator<(const node &x)const {
		if(w==x.w)return d<x.d;
		return w<x.w;
	}
}e[N];

priority_queue<node> q;
bool cmp(node a,node b){
	return a.s<b.s;
}

sort(e+1,e+1+k,cmp);
	int id=1;
	g[0]=1;
	for(int i=1;i<=n;i++){
		while(e[id].s<=i&&id<=k){
			q.push(e[id++]);
		}
		if(q.empty())g[i]=i+1;
		else{
			node u=q.top();
			if(u.t<i){
				i--;
				q.pop();
				continue;
			}
			g[i]=u.d+1;
			h[i]=u.w;
		}
	}

然后 dp 即可

设 \(dp_{i,j}\) 表示 选到第 \(i\) 秒 ， 用了 \(j\) 次技能的最小钱数

	for(int i=0;i<=n;i++){
		for(int j=0;j<=m;j++){
			f[i+1][j+1]=min(f[i+1][j+1],f[i][j]);//用了技能
			f[g[i]][j]=min(f[g[i]][j],f[i][j]+h[i]);
		}
	}

为什么是扩展？ 不扩展怎么处理 g[i] ?

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5;
int n,m,k;
struct node{
	int s,t,d,w;
	bool operator<(const node &x)const {
		if(w==x.w)return d<x.d;
		return w<x.w;
	}
}e[N];
int g[N],f[N][205],h[N];
priority_queue<node> q;
bool cmp(node a,node b){
	return a.s<b.s;
}
signed main(){
	cin>>n>>m>>k;
	for(int i=1;i<=k;i++){
		cin>>e[i].s>>e[i].t>>e[i].d>>e[i].w;
	}
	sort(e+1,e+1+k,cmp);
	int id=1;
	g[0]=1;
	for(int i=1;i<=n;i++){
		while(e[id].s<=i&&id<=k){
			q.push(e[id++]);
		}
		if(q.empty())g[i]=i+1;
		else{
			node u=q.top();
			if(u.t<i){
				i--;
				q.pop();
				continue;
			}
			g[i]=u.d+1;
			h[i]=u.w;
		}
	}
	memset(f,0x3f,sizeof(f));
	f[0][0]=0;
	for(int i=0;i<=n;i++){
		for(int j=0;j<=m;j++){
			f[i+1][j+1]=min(f[i+1][j+1],f[i][j]);
			f[g[i]][j]=min(f[g[i]][j],f[i][j]+h[i]);
		}
	}
	int ans=0x7f7f7f7f7f7f7f	;
	for(int i=0;i<=m;i++)ans=min(ans,f[n+1][i]);
	cout<<ans;
	return 0;
}

坑点：最大值开小了……

F

不会让核弹做即可