牛客2-H施魔法|线段树优化dp，维护区间最小值

状态转移方程

题目地址：https://ac.nowcoder.com/acm/contest/3003/H

先排序。
假设f[i-1] 表示用掉前i-1个元素的最小代价，那么考虑用第i个元素的最小代价，肯定由前面的第j个元素来推出来的，
可以由哪些元素推出呢，因为至少拿k个，所以j的范围就是1~i-k+1，这样就可以至少留下 i-(i-k-1)+1 = k个元素组成一组了。

f[i] = min(f[j-1] + (a[i] - a[j] ) j∈1~i-k+1
即f[i] = min(f[j-1] - a[j]) + a[i]

所以只需要维护f[j-1] - a[j]的最小值就行。

使用线段树优化dp

使用线段树维护min(f[j-1] - a[j])
也就是维护前缀区间最小值，dp[i-1] - a[i]

这样O(n)递推，每次O(logn)查询min(dp[1~j-a[j+1])的最小值,且这里j∈[1,i-k+1]
总复杂度O(nlogn)

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 3e5+10;
int n,k;
ll a[maxn];
ll dp[maxn];

/*
f[i] = min(f[j-1] + (a[i] - a[j] )   j∈1~i-k+1
f[i] = min(f[j-1] - a[j]) + a[i]

f[j-1] - a[j] 可以维护这个min
每次查询1 ~ i-k+1 的 min(f[j-1] - a[i] ) 

dp[i] = min(dp[i],dp[j-1] -a[j])+a[i] ;

用线段树叶子结点维护dp[j-1]-a[j] 也就是 dp[i-1] - a[i]的最小值
每次O(logn)查询1~j  j∈1~i-k+1的最小值
更新叶节点dp[i-1] - a[i]即可
 
*/

ll minv[maxn<<2];

void pushup(int o){
    minv[o] = min(minv[o<<1],minv[o<<1|1]);
}
//建树 
void build(int o,int l,int r){
    if(l == r) { //到最后一行了 [1,1] [2,2] ... 
//        minv[o] = a[l];
        return;
    }
    int mid = (l+r)>>1; 
    build(o<<1,l,mid);
    build(o<<1|1,mid+1,r);
    pushup(o);//向上合并 
}


//a[x] += y : update(1,1,n,x,y); 
//单点修改  o为当前到达节点的编号 
void update(int o,int l,int r,int pos,ll v){
    if(l == r){
        minv[o] += v;
        return;
    }   
    int mid = (l+r)>>1;
    if(pos <= mid) update(o<<1,l,mid,pos,v);//前半段区间
    else update(o<<1|1,mid+1,r,pos,v); //后半段区间
    pushup(o); //向上更新  有一些线段树维护了多个值,所以pushup不止一条 
}

//区间查询 
ll query(int o,int l,int r,int ql,int qr){
    if(ql<=l && r<=qr) return minv[o];//要查询的区间完全包含了[l,r] 
    ll ans = 1e9+7; //为了求区间最小 初始要设置一个比较大的值 
    int mid = (l+r)>>1;
    if(ql<=mid) ans = min(ans,query(o<<1,l,mid,ql,qr));
    if(qr>mid) ans = min(ans,query(o<<1|1,mid+1,r,ql,qr));
    return ans;
}

int main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++) cin>>a[i];
	sort(a+1,a+n+1);
	build(1,1,n);
	for(int i=1;i<=n;i++) dp[i] = (ll)1e18;
	dp[k] = a[k] - a[1];
	//f[i] = min(f[j-1] - a[j]) + a[i] 
	//使用线段树维护f[i-1]+a[i] 总复杂度O(nlogn) 
	for(int i=k;i<=n;i++){ //O(n) 递推 
		ll pre = query(1,1,n,1,i-k+1);  //O(logn) (查询)1~j的最小值 ，这里j∈i-k+1
		dp[i] = min(dp[i],pre + a[i]);
		dp[i] = min(dp[i],a[i] - a[1]);
		update(1,1,n,i,dp[i-1]-a[i]); //O(logn) (更新)dp[i-1]-a[i]的值,从而维护前缀最小值 
	}
	cout<<dp[n];
	return 0;
}