题面

题目描述 有N个村庄坐落在一条直线上，第i(i>1)个村庄距离第1个村庄的距离为Di。需要在这些村庄中建立不超过K个通讯基站，在第i个村庄建立基站的费用为Ci。如果在距离第i个村庄不超过Si的范围内建立了一个通讯基站，那么就成它被覆盖了。如果第i个村庄没有被覆盖，则需要向他们补偿，费用为Wi。现在的问题是，选择基站的位置，使得总费用最小。

输入 输入文件的第一行包含两个整数N,K，含义如上所述。

   第二行包含N-1个整数，分别表示D2,D3,…,DN ，这N-1个数是递增的。

   第三行包含N个整数，表示C1,C2,…CN。

   第四行包含N个整数，表示S1,S2,…,SN。

   第五行包含N个整数，表示W1,W2,…,WN。

输出 输出文件中仅包含一个整数，表示最小的总费用。

样例输入 3 2
1 2
2 3 2
1 1 0
10 20 30
样例输出
4
提示
40%的数据中，N<=500；
100%的数据中，K<=N，K<=100，N<=20,000，Di<=1000000000，Ci<=10000，Si<=1000000000，Wi<=10000。

题解

看题目意思是求费用最小，并且不必输出方案。 让人容易想到DP，不难想到DP方程式为f[i][j]表示第i个基站键在j，区间[1,j]的花费，转移为f[i][j]=min{f[i][k]+cost[k][j]}+c[j]。（cost[k][j]表示区间[k,j]中需要的赔偿总额）然后优化空间，我们直接在最外维枚举一位i，表示建第i个基站，然后压去DP式子中一维，就变成了f[j]=min{f[k]+cost[k][j]}+c[j]。这个做法效率是O（n^2 k）的，显然过不去。 考虑优化。不难发现f[k]+cost[k][j]是转移中最难处理的，因此想在这里做优化。（具体怎么优化我没想到，单经过大神指点，和几篇题解才明白） 首先设g[k]=f[k]+cost[k][j],然后用线段树维护g[k]。在维护g[k]前要先处理两个数组l[i]和r[i]表示村庄i要被覆盖基站的第一个位置和最后一个位置（就是村庄i要被覆盖的话最左能建基站的位置和最右能建基站的位置）这两个数组可以用二分查找很容易处理（毕竟D[i]是单调的）。然后我们考虑，假设在村庄x建基站，那我们就要用x进行转移，在处理完x后，处理x+1前，我们要将r[i]=x的村庄i找出来（这里可以用邻接表将r[i]相同的存起来），然后在**[1,l[i]-1]这段区间上加上w[i],这是因为我们是在从前往后处理，x会逐渐增大，所以对于那些左端点无法被基站覆盖的村庄，随着x的后移左端点也不会被覆盖，所以要加上赔偿的代价。这样我们就可以用线段树维护g[k]了，然后每次都在[1,i-1]上查询g[k]的min值即可。最后加一点，为了防止遗漏，需要在最后加上一个D[i]=S[i]=inf**的村庄，因为每次转移时只考虑了i对其之前的影响，并没有考虑到它对它之后的影响。

#include<iostream>
#include<algorithm>
#include<cstdio>
#define maxn 20005
#define inf 1000000009
using namespace std;
int n,m,d[maxn],c[maxn],s[maxn],w[maxn],f[maxn],g[maxn*4],lazy[maxn*4],l[maxn],r[maxn],Ans=100000009;
int hd[maxn],v[maxn],nx[maxn],cnt;
inline void add(int ra,int x){v[++cnt]=x,nx[cnt]=hd[ra];hd[ra]=cnt;}
inline void scan(int a[]){for(int i=1;i<=n;i++) scanf("%d",&a[i]);}
inline void update(int x){g[x]=min(g[x*2],g[x*2+1]);}
inline void build(int id,int l,int r){
	lazy[id]=0;
	if(l==r){g[id]=f[l];return;}
	int mid=(l+r)/2;
	build(id*2,l,mid);
	build(id*2+1,mid+1,r);
	update(id);
}
inline void pushdown(int id){
	if(!lazy[id]) return;
	g[id*2]+=lazy[id];
	g[id*2+1]+=lazy[id];
	lazy[id*2]+=lazy[id];
	lazy[id*2+1]+=lazy[id];;
	lazy[id]=0;
}
inline void modify(int id,int l,int r,int ql,int qr,int val){
	if(ql>qr) return;
	if(ql<=l&&qr>=r){
		g[id]+=val;
		lazy[id]+=val;
		return;
	}
	pushdown(id);
	int mid=(l+r)/2;
	if(ql<=mid) modify(id*2,l,mid,ql,qr,val);
	if(qr>mid) modify(id*2+1,mid+1,r,ql,qr,val);
	update(id);
}
inline int query(int id,int l,int r,int ql,int qr){
	if(ql>qr) return 0;
	if(ql<=l&&qr>=r) return g[id];
	pushdown(id);
	int mid=(l+r)/2;
	int ans=inf;
	if(ql<=mid) ans=min(ans,query(id*2,l,mid,ql,qr));
	if(qr>mid) ans=min(ans,query(id*2+1,mid+1,r,ql,qr));
	return ans;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=2;i<=n;i++) scanf("%d",&d[i]);
	scan(c),scan(s),scan(w);
	m++;n++;w[n]=d[n]=s[n]=inf;
	for(int i=1;i<=n;i++){
		l[i]=lower_bound(d+1,d+n+1,d[i]-s[i])-d;
		r[i]=lower_bound(d+1,d+n+1,d[i]+s[i])-d;
		if(d[r[i]]>d[i]+s[i]) r[i]--;
		add(r[i],i);
	}
	for(int i=1;i<=m;i++){
		if(i==1){
			int t=0;
			for(int j=1;j<=n;j++){
				f[j]=t+c[j];
				for(int k=hd[j];k;k=nx[k]) t+=w[v[k]];
			}
			Ans=min(Ans,f[n]);
			continue;
		}
		build(1,1,n);
		for(int j=1;j<=n;j++){
			f[j]=query(1,1,n,1,j-1)+c[j];
			for(int k=hd[j];k;k=nx[k]) modify(1,1,n,1,l[v[k]]-1,w[v[k]]);
		}
		Ans=min(Ans,f[n]);
	}
	printf("%d\n",Ans);
	return 0;
}

（嗯，第一次发题解，讲的不好还请指出）