Optimal Milking[USACO2013 Dec]
【题目描述】
Farmer John最近购买了$N(1 \leq N \leq 40000)$台挤奶机，编号为$1 \sim N$，并排成一行。第$i$台挤奶机每天能够挤$M(i)$单位的牛奶$(1 \leq M(i) \leq 100,000)$。由于机器间距离太近，使得两台相邻的机器不能在同一天使用。Farmer John可以自由选择不同的机器集合在不同的日子进行挤奶。
在$D(1 \leq D \leq 50,000)$天中，每天Farmer John对某一台挤奶机进行维护，改变该挤奶机的产量。
Farmer John希望设计一个挤奶方案，使得挤奶机能够在D天后获取最多的牛奶。
【输入格式】
第$1$行：两个整数$N$和$D$
第$2\dots N+1$行：每台挤奶机的$M(i)$
第$N+2\dots N+D+1$行：两个整数$i$和$m$，表示每天对机器$i$进行维护，机器$i$的产量为$m$。
【输出格式】
输出最大产量。
题解
不知道这种题目能不能叫区间DP。。。在线段树上区间DP?
对于线段树的每个节点 我们维护一个$f[2][2]$
其中$f[0][0]$表示区间左端点不选 右端点也不选时的最大区间和$f[0][1]$表示左端点不选 右端点选 剩下两个也类似
那么我们要把一个节点的左右儿子合并来更新当前节点 怎么来合并这个$f[2][2]$呢？
为了方便起见 我们这里假设当前节点$x$的左儿子是$l$，右儿子是$r$
那么$x.f[0][0] = max(l.f[0][0]+r.f[0][0],l.f[0][1]+r.f[0][0],l.f[0][0]+r.f[1][0])$
感觉是不是少了什么？为什么没有$l.f[0][1]+r.f[1][0]$？
这个是不合法的 因为题目要求相邻两个不能同时选择 而左儿子区间的右端点和右儿子区间的左端点当然是相邻的
剩下3个转移也同理 为了更清楚一点这里还是写出来
$x.f[0][1] = max(l.f[0][0]+r.f[0][1],l.f[0][1]+r.f[0][1],l.f[0][0]+r.f[1][1])$
$x.f[1][0] = max(l.f[1][0]+r.f[0][0],l.f[1][1]+r.f[0][0],l.f[1][0]+r.f[1][0])$
$x.f[1][1] = max(l.f[1][0]+r.f[0][1],l.f[1][1]+r.f[0][1],l.f[1][0]+r.f[1][1])$
ok 对于叶子节点$f[0][0]=0$$f[1][1]=M(i)$$f[0][1]$和$f[1][0]$都是不合法的(因为叶子节点的区间就只有一个元素) 所以设成负无穷
单点修改只需要改叶子的$f[1][1]$就可以了 那么此题就做完了
ps.合并$f$数组时注意如果转移得到某个$f[i][j]$比负无穷还小了 就把$f[i][j]$重新设为负无穷 防止负无穷加爆了
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 0x3f3f3f3f3f3f3f3f;
int n, d;
ll a[40005], ans;
struct segtree{
struct tree{
int l, r;
ll f[2][2];
} tr[400005];
#define lson ind<<1
#define rson ind<<1|1
inline void pushup(int ind) {
tr[ind].f[0][0] = max(max(tr[lson].f[0][1] + tr[rson].f[0][0], tr[lson].f[0][0] + tr[rson].f[1][0]), tr[lson].f[0][0] + tr[rson].f[0][0]);
tr[ind].f[0][1] = max(max(tr[lson].f[0][1] + tr[rson].f[0][1], tr[lson].f[0][0] + tr[rson].f[1][1]), tr[lson].f[0][0] + tr[rson].f[0][1]);
tr[ind].f[1][0] = max(max(tr[lson].f[1][1] + tr[rson].f[0][0], tr[lson].f[1][0] + tr[rson].f[1][0]), tr[lson].f[1][0] + tr[rson].f[0][0]);
tr[ind].f[1][1] = max(max(tr[lson].f[1][1] + tr[rson].f[0][1], tr[lson].f[1][0] + tr[rson].f[1][1]), tr[lson].f[1][0] + tr[rson].f[0][1]);
for (int i = 0; i <= 1; i++) for (int j = 0; j <= 1; j++) tr[ind].f[i][j] = max(tr[ind].f[i][j], -inf);
}
void build(int ind, int l, int r) {
tr[ind].l = l, tr[ind].r = r;
for (int i = 0; i <= 1; i++) for (int j = 0; j <= 1; j++) tr[ind].f[i][j] = -inf;
if (l == r) {
tr[ind].f[0][0] = 0;
tr[ind].f[1][1] = a[l];
return;
}
int mid = (l + r) >> 1;
build(lson, l, mid); build(rson, mid+1, r);
pushup(ind);
}
void update(int ind, int pos, ll x) {
int l = tr[ind].l, r = tr[ind].r;
if (l == r) {
tr[ind].f[1][1] = x;
return;
}
int mid = (l + r) >> 1;
if (pos <= mid) update(lson, pos, x);
else update(rson, pos, x);
pushup(ind);
}
} T;
int main() {
scanf("%d %d", &n, &d);
for (int i = 1; i <= n; i++) {
scanf("%lld", &a[i]);
}
T.build(1, 1, n);
for (int i = 1; i <= d; i++) {
int pos, v;
ll nowans = 0;
scanf("%d %d", &pos, &v);
T.update(1, pos, v);
nowans = max(nowans, T.tr[1].f[0][0]);
nowans = max(nowans, T.tr[1].f[0][1]);
nowans = max(nowans, T.tr[1].f[1][0]);
nowans = max(nowans, T.tr[1].f[1][1]);
ans += nowans;
}
printf("%lld\n", ans);
return 0;
}
|
