链接：
题目大意：
在 (n) 个点里建不超过 (k) 个基站，每个点的位置是 (d_i)，在 (i) 建基站的钱是 (c_i)，如果在 (i) 不超过 (s_i) 的范围内没有基站，就要再付 (w_i)。求最小费用。
正文：
考虑动态规划。设 (f_{i,j}) 表示在第 (i) 个点建第 (j) 个基站的最小费用。则有：
[f_{i,j}=min_{k<i}{f_{k,j-1}+cost_{k,i}}
]
其中 (cost_{k,i}) 表示从 (k) 到 (i) 没有覆盖到的点的 (w) 值总和。我们的主要问题，就是求解这个 (cost_{k,i})。
先二分出 (i) 的范围 (l_i,r_i)。那么若在 (j) 点建基站，有 (r_i<d_j) 的话费用就要加上 (w_i)，这一步可以用邻接表实现。
还有一种情况就是，从 ([1,l_i)) 转移过来的话，要费用要加上 (w_i)。那么可以用线段树实现。
由于在转移过程中总是是从 (j-1) 过来的，那么可以滚动数组。
代码:
int n, k;
ll f[N];
struct SegmentTree
{
struct node
{
int l, r;
ll val, lazy;
} t[N << 2];
void build(int p, int l, int r)
{
t[p].l = l, t[p].r = r;
t[p].lazy = 0;
if (t[p].l == t[p].r)
{
t[p].val = f[l];
return ;
}
int mid = t[p].l + t[p].r >> 1;
build (p << 1, l, mid);
build (p << 1 | 1, mid + 1, r);
t[p].val = min(t[p << 1].val, t[p << 1 | 1].val);
}
void spread(int p)
{
if (!t[p].lazy) return;
t[p << 1].val += t[p].lazy;
t[p << 1].lazy += t[p].lazy;
t[p << 1 | 1].val += t[p].lazy;
t[p << 1 | 1].lazy += t[p].lazy;
t[p].lazy = 0;
}
void modify(int p, int l, int r, ll val)
{
if (l <= t[p].l && t[p].r <= r)
{
t[p].val += val;
t[p].lazy += val;
return ;
}
spread(p);
int mid = t[p].l + t[p].r >> 1;
if (l <= mid) modify (p << 1, l, r, val);
if (mid < r) modify (p << 1 | 1, l, r, val);
t[p].val = min(t[p << 1].val, t[p << 1 | 1].val);
}
ll query(int p, int l, int r)
{
if (l <= t[p].l && t[p].r <= r)
return t[p].val;
spread(p);
int mid = t[p].l + t[p].r >> 1;
ll ans = 1ll << 30;
if (l <= mid) ans = min (ans, query (p << 1, l, r));
if (mid < r) ans = min (ans, query (p << 1 | 1, l, r));
t[p].val = min(t[p << 1].val, t[p << 1 | 1].val);
return ans;
}
}t;
ll s[N], c[N], d[N], w[N], l[N], r[N];
struct edge
{
int to, nxt;
}e[N];
int head[N], tot;
void add(int u, int v) {e[++tot] = (edge){v, head[u]}, head[u] = tot;}
int main()
{
scanf ("%d%d", &n, &k);
for (int i = 2; i <= n; i++) scanf ("%lld", &d[i]);
for (int i = 1; i <= n; i++) scanf ("%lld", &c[i]);
for (int i = 1; i <= n; i++) scanf ("%lld", &s[i]);
for (int i = 1; i <= n; i++) scanf ("%lld", &w[i]);
n++; d[n] = w[n] = 0x3f3f3f3f;
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[i] + s[i] < d[r[i]]) r[i]--;
add(r[i], i);
}
ll sum = 0;
for (int i = 1; i <= n; i++)
{
f[i] = sum + c[i];
for (int j = head[i]; j; j = e[j].nxt)
sum += w[e[j].to];
}
ll ans = f[n];
for (int j = 2; j <= k + 1; j++)
{
t.build(1, 1, n);
for (int i = 1; i <= n; i++)
{
f[i] = (i >= j? t.query(1, j - 1, i - 1): 0) + c[i];
for (int g = head[i]; g; g = e[g].nxt)
if(l[e[g].to] > 1) t.modify(1, 1, l[e[g].to] - 1, w[e[g].to]);
}
ans = min(ans, f[n]);
}
printf ("%lld
", ans);
return 0;
}