P2605 [ZJOI2010]基站选址
线段树优化 dp。
记 f i , j f_{i,j}fi,j 表示第 i ii 位置建第 j jj 个基站的最小费用。
则有：f i , j = min k = 1 i − 1 ( f k , j − 1 + c o s t k , i ) f_{i,j}=\min\limits_{k=1}^{i-1}(f_{k,j-1}+cost_{k,i})fi,j=k=1mini−1(fk,j−1+costk,i)，其中 c o s t i , j cost_{i,j}costi,j 表示 k , i k,ik,i 两点间没有基站的赔偿费用。
另，要在 + ∞ +\infty+∞ 位置建立一个费用为 0 00，覆盖距离为 0 00 的基站，起到统计答案的作用。
时间复杂度 O ( n 3 k ) \mathcal O(n^3k)O(n3k)。
考虑优化，发现 min \minmin 即区间最小值，可用线段树优化。
记 s t i , e d i st_i,ed_isti,edi 分别表示在区间 [ d i − s i , d i + s i ] [d_i-s_i,d_i+s_i][di−si,di+si] 的点的最小及最大编号。
若当前枚举的点 i = e d k i=ed_ki=edk，那么线段树上区间 [ 1 , s t k − 1 ] [1,st_k-1][1,stk−1] 加上 w k w_kwk。
因为后面的点要是从 [ 1 , s t k − 1 ] [1,st_k-1][1,stk−1] 的点转移，那么 k kk 就无法被覆盖到，所以要加上赔偿费用。
最后区间查询最小值即可。
时间复杂度 O ( n k log n ) \mathcal O(nk \log n)O(nklogn)。
具体见代码。
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int _ = 2e4 + 10, inf = 2e18;
int n, k, d[_], c[_], s[_], w[_];
int st[_], ed[_];
vector<int> D[_];
int tr[_ << 2], tag[_ << 2];
int f[_];
void build(int o, int l, int r)
{
tag[o] = 0;
if(l == r)
{
tr[o] = f[l];
return;
}
int mid = (l + r) >> 1;
build(o << 1, l, mid);
build(o << 1 | 1, mid + 1, r);
tr[o] = min(tr[o << 1], tr[o << 1 | 1]);
}
void update(int o, int l, int r, int L, int R, int val)
{
if(L > R) return;
if(L <= l && r <= R)
{
tr[o] += val, tag[o] += val;
return;
}
int mid = (l + r) >> 1;
if(L <= mid) update(o << 1, l, mid, L, R, val);
if(R > mid) update(o << 1 | 1, mid + 1, r, L, R, val);
tr[o] = min(tr[o << 1], tr[o << 1 | 1]) + tag[o];
}
int query(int o, int l, int r, int L, int R, int v)
{
if(L > R) return inf;
if(L <= l && r <= R)
return tr[o];
int mid = (l + r) >> 1, res = 0;
if(L <= mid) res = query(o << 1, l, mid, L, R, v + tag[o]);
if(R > mid) res = min(res, query(o << 1 | 1, mid + 1, r, L, R, v + tag[o]));
return res;
}
signed main()
{
scanf("%lld%lld", &n, &k);
d[1] = 0;
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++, k++;
d[n] = w[n] = inf;
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]--;
D[ed[i]].push_back(i);
}
int now = 0;
for(int i = 1; i <= n; ++i)
{
f[i] = now + c[i];
for(int j : D[i])
now += w[j];
}
int ans = f[n];
for(int i = 2; i <= k; ++i)
{
build(1, 1, n);
for(int j = 1; j <= n; ++j)
{
f[j] = query(1, 1, n, 1, j - 1, 0) + c[j];
for(int k : D[j])
update(1, 1, n, 1, st[k] - 1, w[k]);
}
ans = min(ans, f[n]);
}
printf("%lld\n", ans);
return 0;
}