【题目分析】
一条直线上给定相对距离Di（距第一个村庄的距离）的N个村庄中建K个基站，每个村庄i接收的范围为前后Si，建基站费用Ci，一个村庄要么被接受到要么额外支付Wi。设计方案求最小总费用。
【算法分析】
朴素方程为f[i][j](前i个村庄中选j个基站，第j个建在i)=MIN(f[k][j-1]+W[k+1..j](表示k+1..j村庄中建一个基站后覆盖所有k+1..j（没覆盖就支付费用）所需的最小总和)).W预处理需要N^3时间，DP需要N^2*K的时间。显然需要优化。
其实这样一个“裸”的方程看起来似乎很难再在时间上优化下去，因为该算法的瓶颈在于预处理的“复杂”（预处理涉及到题中的C、S、W）。这时，我们就需要对方程进行改变，让其显得更加“简洁”。f[i][j](前i个村庄中选j个基站，第j个建在i)=MIN(f[k][j-1]+W[k+1..j]（k+1..j中k和i都覆盖不到的村庄的W和）+Ci。Ci为常数，DP又可以滚动优化，所以方程实际上要干的事就是f[i]=MIN(f[k]+W[k+1..j])。为了计算方便，我们可以再在最后面设一个村庄n+1，k增加1，令d[n+1]=INF。那么基站数量一定下，最优解就是f[n]。
显然现在我们对于每个村庄，都可以在O(logn)的时间内二分查找出它向前向后最多能覆盖到的地方，这个预处理在后面的分析中会用到。
我们进一步分析W[k+1..j]的计算。显然一个村庄p覆盖不到的条件是同时满足Dp+Sp<Di,Dp-Sp>Dk.现在我们假设有一个k，一个i，考虑覆盖到的村庄。
我们现在假设k不变，i增大1，那么会发生什么变化？很显然，原本被k覆盖到的村庄还是被覆盖的，但被i覆盖到的村庄左边一部分没有被覆盖了，也就意味着这些村庄需要另外给付钱了！回到那个条件，我们发现这便是Di单调递增使得一些原本覆盖到的村庄p覆盖不到了！如果我们已知W[k+1..i]，怎么求出W[k+1..i+1]？很显然的，加上新增的村庄的W即可。
当然，事情还没那么简单，由于我们DP时是固定i求一个k使解最小，自然而然我们可以初步想到一个思路用线段树维护每个f[k]+W[k+1..j]的值，“新增的村庄”打个标记加上去就行。
算法流程：
读入，预处理每个村庄向前向后最多能覆盖到的地方记为st[i],ed[i]
循环j=1..k表示当前建第几个村庄
利用上次的f（即每个点的初值）建线段树
清空旧的f
循环i=1..n
查找线段树中0..i-1里f的最小值
最小值+Ci后赋值给f[i]
对于i，若ed[x]=i，则在线段树中0..st[x]-1集体加上Wx
(原因：考虑每个x（满足ed[x]=i，具体实现可用链表（数组模拟）），这样做是为 了对于i后面的村庄如果选定村庄k，且x够不到（x原本刚刚好能被i覆盖）， 那么这个k的f[k]就要加上Wx了。）
用当前的f[n]更新最优解
输出最优解
时间复杂度O(knlogn)
空间复杂度O(n)
【总结】
DP优化，突破口就是利用了Di单调递增的性质，并合理使用数据结构加以优化。
【吐槽】
算法分析第二段及之后均为看题解后总结得来。
【附程序】
#include<cstdio>
#include<cstring>
#define rep(i,x,y) for(i=x;i<=y;i++)
#define rep_(i,x,y) for(i=x;i>=y;i--)
#define MIN(x,y) ((x)<(y)?(x):(y))
#define MAX(x,y) ((x)>(y)?(x):(y))
using namespace std;
const int INF=~0U>>2;
const int MAXN=20010;
const int MAXK=102;
typedef int arr[MAXN];
int n,k,i,j,pos,ans,min0,en0;
arr d,c,s,w,f,st,ed;
struct tree
{
int min[1<<16],en[1<<16];
void pdown(int i)
{
en[i<<1]+=en[i];min[i<<1]+=en[i];
en[(i<<1)+1]+=en[i];min[(i<<1)+1]+=en[i];
en[i]=0;
}
void pup(int i)
{
min[i]=MIN(min[i<<1],min[(i<<1)+1]);
}
void build(int i,int x,int y)
{
en[i]=0;
if(x!=y)
{
build(i<<1,x,(x+y)>>1);
build((i<<1)+1,((x+y)>>1)+1,y);
pup(i);
}
else min[i]=f[x];
}
void find(int i,int x,int y,int l,int r,int kind)
{
if(x>y)return;
if(l>y || r<x)return;
if(x>=l && y<=r)
{
switch(kind)
{
case 1: //查找最小值
min0=MIN(min0,min[i]);
break;
case 2: //加上一个值
en[i]+=en0;min[i]+=en0;
break;
}
}
else
{
pdown(i);
find(i<<1,x,(x+y)>>1,l,r,kind);
find((i<<1)+1,((x+y)>>1)+1,y,l,r,kind);
pup(i);
}
}
}a;
struct biao
{
int edge;
arr e,b,first,last,w;
void clean()
{
edge=0;
memset(first,-1,sizeof(first));
memset(b,-1,sizeof(b));
}
void add(int x,int y,int z)
{
e[edge]=y;w[edge]=z;
if(first[x]==-1)first[x]=edge;
else b[last[x]]=edge;
last[x]=edge++;
}
}q;
int findl(int x)
{
int l,r;
for(l=1,r=n;l<r;)
{
if(x<=d[(l+r)>>1])r=(l+r)>>1;
else l=((l+r)>>1)+1;
}
return l;
}
int findr(int x)
{
int l,r;
for(l=1,r=n;l<r;)
{
if(x>=d[(l+r+1)>>1])l=(l+r+1)>>1;
else r=((l+r+1)>>1)-1;
}
return l;
}
int main()
{
freopen("base.in","r",stdin);
freopen("base.out","w",stdout);
scanf("%d%d",&n,&k);
rep(i,2,n)scanf("%d",&d[i]);
rep(i,1,n)scanf("%d",&c[i]);
rep(i,1,n)scanf("%d",&s[i]);
rep(i,1,n)scanf("%d",&w[i]);
n++;d[n]=INF;k++;
q.clean();
rep(i,1,n)
{
st[i]=findl(d[i]-s[i]);
ed[i]=findr(d[i]+s[i]);
q.add(ed[i],st[i]-1,w[i]);
}
ans=INF;
f[0]=0;rep(i,1,n)f[i]=INF;
rep(j,1,k)
{
a.build(1,0,n);
f[0]=0;rep(i,1,n)f[i]=INF;
rep(i,1,n)
{
min0=INF;
a.find(1,0,n,0,i-1,1);
f[i]=min0+c[i];
for(int pos=q.first[i];pos>=0;pos=q.b[pos])
{
en0=q.w[pos];
a.find(1,0,n,0,q.e[pos],2);
}
}
ans=MIN(ans,f[n]);
}
printf("%d\n",ans);
scanf("\n");
return 0;
}