神TM毒瘤线段树优化DP......新姿势get。
题意：有n个村庄，在里面选不多于k个建立基站。
建立基站要ci的费用。如果一个村庄方圆si内没有基站，那么又要支出wi的费用。求最小费用。
解：很显然想到DP，f[i][j]表示前i个村庄里面放了j个基站，其中第i个一定选的最小费用。费用只统计不超过i的。
转移就是枚举从p转移，对于p到i的每一个，检查是否需要付钱。
这样是n³k的，只有20分。
#include <cstdio>
#include <algorithm> typedef long long LL;
const int N = ;
const LL INF = 0x3f3f3f3f3f3f3f3f; LL d[N], s[N], f[N][], c[N], w[N];
int n, first[N], last[N]; inline LL val(int l, int r) {
LL ans = ;
for(int i = l + ; i < r; i++) {
if(l < first[i] && r > last[i]) {
ans += w[i];
}
}
return ans;
} int main() {
int k;
LL ans = ;
scanf("%d%d", &n, &k);
for(int i = ; i <= n; i++) {
scanf("%lld", &d[i]);
}
for(int i = ; i <= n; i++) {
scanf("%lld", &c[i]);
}
for(int i = ; i <= n; i++) {
scanf("%lld", &s[i]);
}
for(int i = ; i <= n; i++) {
scanf("%lld", &w[i]);
ans += w[i];
f[i][] = f[i - ][] + w[i];
} for(int i = ; i <= n; i++) { // prework
int l = , r = i;
while(l < r) {
int mid = (l + r) >> ;
if(d[mid] >= d[i] - s[i]) {
r = mid;
}
else {
l = mid + ;
}
}
first[i] = r;
l = i;
r = n;
while(l < r) {
int mid = (l + r + ) >> ;
if(d[mid] <= d[i] + s[i]) {
l = mid;
}
else {
r = mid - ;
}
}
last[i] = r;
} for(int j = ; j <= k + ; j++) {
for(int i = ; i <= n + ; i++) {
// f[i][j] = std::min(f[p][j - 1] + val
if(j == ) {
f[i][j] = c[i] + val(, i);
}
else {
f[i][j] = INF;
for(int p = j - ; p < i; p++) {
f[i][j] = std::min(f[i][j], f[p][j - ] + val(p, i) + c[i]);
}
}
}
if(j > ) {
ans = std::min(ans, f[n + ][j]);
}
} printf("%lld", ans);
return ;
}
20分代码
然后我又想到了网络流，发现好像可以搞成最大权闭合子图来做，但是那个k的限制不好处理.....
最后光荣爆0了。
正解是线段树优化DP，但是怎么个优化法呢？
转移方程：f[i][j] = f[p][j - 1] + val(p, i) + c[i]
黑科技就是用线段树维护等式右边......下标就是p。
具体来说，我们当前正在考虑i。
那么f[i][j]就是min(0, i - 1)，直接在线段树上查询即可。
线段树的初始值是f[p][j - 1]，我们要动态的加上val(p, i)
每个点都有一个last，表示在i ~ last这段区间建基站的话能覆盖到它。
设last[v] = i，那么在i及之前的DP值都不会加上w[v]，因为v之前的不会考虑到v，v ~ i的会覆盖到v。
i及之后的，有一部分转移要加上w[v]，就是first[v]之前的部分。
因为first ~ i的转移会覆盖v，而i之后的转移会计算v。所以这些都不用计算v。
此时我们把0 ~ first[v] - 1的区间全部加上w[i]即可。
然后每次循环一个新j的时候把线段树初始化。
细节处理繁多......
#include <cstdio>
#include <algorithm>
#include <vector> typedef long long LL;
const int N = ;
const LL INF = 0x3f3f3f3f3f3f3f3f; LL d[N], s[N], f[N][], c[N], w[N];
int n, first[N], last[N], Time;
std::vector<int> v[N]; LL small[N << ], tag[N << ]; inline void pushup(int o) {
small[o] = std::min(small[o << ], small[o << | ]);
return;
} inline void pushdown(int o) {
if(tag[o]) {
int ls = o << ;
int rs = ls | ;
tag[ls] += tag[o];
tag[rs] += tag[o];
small[ls] += tag[o];
small[rs] += tag[o];
tag[o] = ;
}
return;
} void add(int L, int R, LL v, int l, int r, int o) {
if(L <= l && r <= R) {
tag[o] += v;
small[o] += v;
return;
}
int mid = (l + r) >> ;
pushdown(o);
if(L <= mid) {
add(L, R, v, l, mid, o << );
}
if(mid < R) {
add(L, R, v, mid + , r, o << | );
}
pushup(o);
return;
} LL ask(int L, int R, int l, int r, int o) {
if(L <= l && r <= R) {
return small[o];
}
int mid = (l + r) >> ;
pushdown(o);
LL ans = INF;
if(L <= mid) {
ans = std::min(ans, ask(L, R, l, mid, o << ));
}
if(mid < R) {
ans = std::min(ans, ask(L, R, mid + , r, o << | ));
}
return ans;
} void clear(int l, int r, int o) {
tag[o] = ;
if(l == r) {
small[o] = f[r - ][Time - ];
return;
}
int mid = (l + r) >> ;
clear(l, mid, o << );
clear(mid + , r, o << | );
pushup(o);
return;
} int main() {
int k;
LL ans = ;
scanf("%d%d", &n, &k);
for(int i = ; i <= n; i++) {
scanf("%lld", &d[i]);
}
for(int i = ; i <= n; i++) {
scanf("%lld", &c[i]);
}
for(int i = ; i <= n; i++) {
scanf("%lld", &s[i]);
}
for(int i = ; i <= n; i++) {
scanf("%lld", &w[i]);
ans += w[i];
f[i][] = f[i - ][] + w[i];
} for(int i = ; i <= n; i++) { // prework
int l = , r = i;
while(l < r) {
int mid = (l + r) >> ;
if(d[mid] >= d[i] - s[i]) {
r = mid;
}
else {
l = mid + ;
}
}
first[i] = r;
l = i;
r = n;
while(l < r) {
int mid = (l + r + ) >> ;
if(d[mid] <= d[i] + s[i]) {
l = mid;
}
else {
r = mid - ;
}
}
last[i] = r;
v[r].push_back(i);
} for(int i = ; i <= n + ; i++) {
f[i][] = INF;
} for(int j = ; j <= k + ; j++) {
Time = j;
clear(, n + , );
for(int i = ; i <= n + ; i++) {
// ask f[i][j]
if(i >= j) {
f[i][j] = ask(, i, , n + , ) + c[i];
}
else {
f[i][j] = INF;
}
// insert
for(int p = ; p < v[i].size(); p++) {
add(, first[v[i][p]], w[v[i][p]], , n + , );
}
}
if(j > ) {
ans = std::min(ans, f[n + ][j]);
}
} printf("%lld", ans);
return ;
}
AC代码
思考：如果si表示能覆盖方圆si的村庄，又如何？
转移方程写出来，发现就是一个简单的前缀最大值优化。要处理一下前缀和为负的这种情况...