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; }
|