有N个村庄坐落在一条直线上，第i(i>1)个村庄距离第1个村庄的距离为\(D_i\)
需要在这些村庄中建立不超过K个通讯基站，在第i个村庄建立基站的费用为\(C_i\)
如果在距离第i个村庄不超过\(S_i\)的范围内建立了一个通讯基站，那么就成它被覆盖了
如果第i个村庄没有被覆盖，则需要向他们补偿，费用为\(W_i\)
现在的问题是，选择基站的位置，使得总费用最小。
用\(f(i,j)\)表示前\(i\)个村庄建了\(j\)个通讯站且第\(j\)个建在\(i\)处的最小代价，容易写出转移式
\[f(i,j)=\min_{k=1}^{i-1}\{f(k,j−1)+cost(k,i)\}+C_i\]
其中\(cost(k,i)\)表示中间的补偿费用
然而这种做法时间是\(O(N \cdot K \cdot N)\)，空间是\(O(N^2)\)的，不可行。
如果我们外层枚举\(j\)，里面枚举\(i\)呢？
很显然\(f\)的第二维和\(cost\)的第一维都可以省略。\(f\)可以用滚动，\(cost\)可以动态更新，因为变化元素的其实是有限（均摊\(O(1)\)）的。
\[f(i)=\min_{k=1}^{i-1}\{f(k)+cost(k)\}+C_i\]
由于一个村庄\(i\)被覆盖的条件是在距离第\(i\)个村庄不超过\(S_i\)的范围内建立了一个通讯基站，因此可以发现能覆盖一个村庄的基站位置应该是一个区间。
考虑第\(i\)个村庄对于的区间\([L,R]\)，如果目前考虑的最后一个基站为\(R\)，要转移到\(R+1\)
如果\(R\)处不建基站，那么对于相对\(R+1\)的上一个基站为\([1,L-1]\)的情况，都无法覆盖当前村庄，因此需要对\(cost\)的\([1,L-1]\)区间加\(W_i\)
如果\(R\)处建基站，那么相当于是在相对\(R+1\)的上一个基站为\([1,R-1]\)中选择一个代价最小的，相当于对之前\(f\)和\(cost\)的和区间查询最小值
用程序的语言来讲，我们用\(st_i\)和\(ed_i\)分别表示\(i\)最左端、最右端可以覆盖到\(i\)的通讯站位置，那么我们会发现当\(ed_x=i\)时，转移到\(i+1\)时\(x\)便覆盖不到了。
我们用线段树维护\(\min\{f(k)+cost(k)\}\)，从\(f(i)\)变到\(f(i+1)\)时对于\(ed_x=i\)的\(x\),线段树中\([1,st_x−1]\)都加上\(W_x\)(加上补偿费用)即可
这样\(f\)就不用滚动了，\(cost\)也不用单独提出来。
外层循环枚举建站个数时每次重建线段树，复杂度\(O(K \cdot N \log N)\)
代码 #include<cstdlib> #include<cstdio> #include<cmath> #include<cstring> #include<ctime> #include<iostream> #include<string> #include<vector> #include<list> #include<deque> #include<stack> #include<queue> #include<map> #include<set> #include<bitset> #include<algorithm> #include<complex> #pragma GCC optimize ("O0") using namespace std; template<class T> inline T read(T&x) { T data=0; int w=1; char ch=getchar(); while(!isdigit(ch)) { if(ch=='-') w=-1; ch=getchar(); } while(isdigit(ch)) data=10*data+ch-'0',ch=getchar(); return x=data*w; } typedef long long ll; const int INF=0x3f3f3f3f; const int MAXN=2e4+7; #define lson (o<<1) #define rson (o<<1|1) int d[MAXN],c[MAXN],s[MAXN],w[MAXN]; int st[MAXN],ed[MAXN]; vector<int> g[MAXN]; int f[MAXN],ans; struct SegTree { int minv[MAXN<<2],addv[MAXN<<2]; // edit 3 void pushup(int o) { minv[o]=min(minv[lson],minv[rson]); } void build(int o,int l,int r) { addv[o]=0; // edit 2 if(l==r) { minv[o]=f[l]; return; } int mid=(l+r)>>1; build(lson,l,mid); build(rson,mid+1,r); pushup(o); } void pushdown(int o) { if(addv[o]) { minv[lson]+=addv[o],addv[lson]+=addv[o]; minv[rson]+=addv[o],addv[rson]+=addv[o]; addv[o]=0; } } int qmin(int o,int l,int r,int ql,int qr) { if(ql>qr) return 0; // cerr<<"query "<<o<<" "<<l<<" "<<r<<" "<<ql<<" "<<qr<<endl; if(ql<=l&&r<=qr) return minv[o]; pushdown(o); int mid=(l+r)>>1,ans=INF; if(ql<=mid) ans=min(ans,qmin(lson,l,mid,ql,qr)); if(qr>=mid+1) ans=min(ans,qmin(rson,mid+1,r,ql,qr)); return ans; } void add(int o,int l,int r,int ql,int qr,int v) { if(ql>qr) return; // cerr<<"add "<<o<<" "<<l<<" "<<r<<" "<<ql<<" "<<qr<<" "<<v<<endl; if(ql<=l&&r<=qr) { minv[o]+=v,addv[o]+=v; return; } pushdown(o); int mid=(l+r)>>1; if(ql<=mid) add(lson,l,mid,ql,qr,v); if(qr>=mid+1) add(rson,mid+1,r,ql,qr,v); pushup(o); } }T; int main() { // freopen(".in","r",stdin); // freopen(".out","w",stdout); int n,m; read(n);read(m); for(int i=2;i<=n;++i) read(d[i]); for(int i=1;i<=n;++i) read(c[i]); for(int i=1;i<=n;++i) read(s[i]); for(int i=1;i<=n;++i) read(w[i]); d[++n]=INF,w[n]=INF,++m; for(int i=1;i<=n;++i) { st[i]=lower_bound(d+1,d+n+1,d[i]-s[i])-d; ed[i]=lower_bound(d+1,d+n+1,d[i]+s[i])-d; if(d[ed[i]]>d[i]+s[i]) --ed[i]; g[ed[i]].push_back(i); } int t=0; for(int i=1;i<=n;++i) { f[i]=t+c[i]; for(int j=0;j<g[i].size();++j) { int x=g[i][j]; t+=w[x]; } } ans=f[n]; for(int i=2;i<=m;++i) { T.build(1,1,n); // edit 1 for(int j=1;j<=n;++j) { f[j]=T.qmin(1,1,n,1,j-1)+c[j]; for(int k=0;k<g[j].size();++k) { int x=g[j][k]; T.add(1,1,n,1,st[x]-1,w[x]); } } ans=min(ans,f[n]); } printf("%d\n",ans); // fclose(stdin); // fclose(stdout); return 0; }