题目
简化题目：1~n个村庄，每个村庄有范围，要求范围内有村庄被选（不超过(k)个），否则被罚款，选村庄有一定花费，求最小总花费
做法
朴素
(dp_{i,j})第(j)个被选的村庄为(i)的最小花费：(dp_{i,k}=min{dp_{j,k-1}+cost_{i,j}}+w_i)
枚举(k)(准备选第(k)个)，(i)(具体选(i))，(j)(上一个被选的)，显然(cost_{i,j})预处理(O(n^2))，枚举方程(O(n^2k))
时间复杂度度估为(O(n^2k))
优化
习惯地，只出现(k)与(k-1)，倒序枚举(j)：(dp_{i}=min{dp_{j}+cost_{i,j}}+w_i)，还只是优化了点空间而已
最外层(k)其实差不多可以不管了((k<=100))，主要是优化刚才的这个方程
无后效性，顺序也显然((j<i))，考虑这部分(min{dp_{j}+cost_{i,j}})，最值有关的（(BIT)/线段树，单调队列，斜率优化......）
有哪些相同的部分可以利用呢？
假设这次是选(x)，上一次选(i)，那(i)前面的我们暂时不管，因为之前已经计算过了，我们只用考虑(i)~(k)中间的赔款
对于上一次选的位置(i)和(j)，如果(i<j)，上一个选(i)的赔款肯定包括了(longrightarrow)上一个选(j)的赔款
理解：(i)~(x)比(j)~(x)中间的空区比较多
已经接近了我们的最终思路，假设我们这次在做第(k)个选(i)，设以(i)为右端点的村庄为(x)，其左端点为(L)，那我们
将(1)~(L-1)都加上(pay_{x})村庄(x)的赔款：选(1)~(L-1)的村庄就不符合(x)
诶！！区间查询最小值及位置，区间修改好像线段树做会比较简单
至此，我们已经得到了最终解法：最外层枚举(k)(选第k个)，第二层枚举选(i)(选第i个村庄)，然后线段树维护选每个点的赔款及区间最小值
My complete code
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
using namespace std;
typedef int LL;
const LL maxn=20000+9,inf=0x3f3f3f3f;
inline LL Read(){
LL x(0),f(1); char c=getchar();
while(c<'0'||c>'9'){
if(c=='-') f=-1;c=getchar();
}
while(c>='0'&&c<='9')
x=(x<<3)+(x<<1)+c-'0',c=getchar();
return x*f;
}
struct node{
LL mn,mni,lazy;
LL son[2];
}T[maxn<<2];
LL n,ans,nod,K,root;
LL d[maxn],s[maxn],bad[maxn],pay[maxn],dp[maxn],st[maxn],ed[maxn];
vector<LL> belong[maxn];
inline void Update(LL now,LL s1,LL s2){
if(T[s1].mn<T[s2].mn)
T[now].mn=T[s1].mn,
T[now].mni=T[s1].mni;
else
T[now].mn=T[s2].mn,
T[now].mni=T[s2].mni;
}
void Build(LL &now,LL l,LL r){
if(!now)
now=++nod;
T[now].mn=T[now].mni=T[now].lazy=0;
if(l==r){
T[now].mn=dp[l],
T[now].mni=l;
return;
}
LL mid(l+r>>1);
Build(T[now].son[0],l,mid),
Build(T[now].son[1],mid+1,r);
Update(now,T[now].son[0],T[now].son[1]);
}
inline void Pushdown(LL now,LL s1,LL s2){
LL val(T[now].lazy);
T[now].lazy=0;
if(!val)
return;
T[s1].lazy+=val,T[s2].lazy+=val,
T[s1].mn+=val,T[s2].mn+=val;
}
LL Query(LL now,LL l,LL r,LL lt,LL rt){
if(lt>rt)
return inf;
if(lt<=l&&rt>=r)
return T[now].mn;
Pushdown(now,T[now].son[0],T[now].son[1]);
LL mid(l+r>>1),ret=inf;
if(lt<=mid)
ret=min(ret,Query(T[now].son[0],l,mid,lt,rt));
if(rt>mid)
ret=min(ret,Query(T[now].son[1],mid+1,r,lt,rt));
return ret;
}
inline void Change(LL now,LL l,LL r,LL lt,LL rt,LL val){
if(lt>rt)
return;
if(lt<=l&&rt>=r){
T[now].mn+=val,
T[now].lazy+=val;
return;
}
Pushdown(now,T[now].son[0],T[now].son[1]);
LL mid(l+r>>1);
if(lt<=mid)
Change(T[now].son[0],l,mid,lt,rt,val);
if(rt>mid)
Change(T[now].son[1],mid+1,r,lt,rt,val);
Update(now,T[now].son[0],T[now].son[1]);
}
int main(){
n=Read(),K=Read();
for(LL i=2;i<=n;++i)
d[i]=Read();
for(LL i=1;i<=n;++i)
pay[i]=Read();
for(LL i=1;i<=n;++i)
s[i]=Read();
for(LL i=1;i<=n;++i)
bad[i]=Read();
d[++n]=inf;
for(LL i=1;i<=n;++i){
st[i]=lower_bound(d+1,d+1+n,d[i]-s[i])-d,
ed[i]=lower_bound(d+1,d+1+n,d[i]+s[i])-d;
if(d[ed[i]]>d[i]+s[i])
--ed[i];
belong[ed[i]].push_back(i);
}
LL sum(0);
for(LL i=1;i<=n;++i){
dp[i]=sum+pay[i];
for(LL j=0,size=belong[i].size();j<size;++j)
sum+=bad[belong[i][j]];
}
ans=dp[n];
++K;
for(LL k=2;k<=K;++k){
Build(root,1,n);
for(LL i=1;i<=n;++i){
dp[i]=Query(root,1,n,1,i-1)+pay[i];
for(LL j=0,size=belong[i].size();j<size;++j){
LL x(belong[i][j]);
Change(root,1,n,1,st[x]-1,bad[x]);
}
}
ans=min(ans,dp[n]);
}
printf("%d
",ans);
return 0;
}