【题目描述】
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)
第(2dots N+1)行：每台挤奶机的(M(i))
第(N+2dots 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])重新设为负无穷 防止负无穷加爆了
代码
#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) { //合并f数组
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); //防止爆long long
}
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
", ans);
return 0;
}