【USACO13DEC】 最优挤奶 - 线段树

题目描述

FJ最近买了1个新仓库, 内含N 个挤奶机,1 到N 编号并排成一行。
挤奶机i 每天能产出M(i) 单位的奶。不幸的是, 机器装得太近以至于如果一台机器i 在某天被使用, 那与它相邻的两台机器那一天不能被使用
(当然, 两端点处的机器分别只有一个与之相邻的机器)。
FJ 可自由选择不同的机器在不同的日子工作。
FJ感兴趣于计算在D 天内他能产出奶的最大值。在每天开始时, 他有足够的时间维护一个选中的挤奶机i, 从而改变它从那天起的每日产奶量M(i)。
给出这些每日的修改,请告诉FJ他D 天中能产多少奶。

题意简述

给定 n 个点排成一排，每个点有一个点权，多次改变某个点的点权并将最大点独立集计入答案，输出最终的答案

思路

记 tree[root][0/1][0/1] 表示以 root 为根的线段树左右区间选/不选的答案
tree[root][0][1] = max(tree[root<<1][0][1]+tree[root<<1|1][0][1],tree[root<<1][0][0]+tree[root<<1|1][0][1],tree[root<<1][0][0]+tree[root<<1|1][1][1])
tree[root][1][0] = max(tree[root<<1][1][0]+tree[root<<1|1][1][0],tree[root<<1][1][1]+tree[root<<1|1][0][0],tree[root<<1][1][0]+tree[root<<1|1][0][0])
tree[root][0][0] = max(tree[root<<1][0][1]+tree[root<<1|1][0][0],tree[root<<1][0][0]+tree[root<<1|1][0][0],tree[root<<1][0][0]+tree[root<<1|1][1][0])
tree[root][1][1] = max(tree[root<<1][1][1]+tree[root<<1|1][0][1],tree[root<<1][1][0]+tree[root<<1|1][1][1],tree[root<<1][1][0]+tree[root<<1|1][0][1])

代码

/************************************************
*Author        :  lrj124
*Created Time  :  2019.11.06.21:55
*Mail          :  1584634848@qq.com
*Problem       :  luogu3097
************************************************/
#include <algorithm>
#include <cstdio>
using namespace std;
const int maxn = 40000 + 10;
int n,d,tree[maxn<<2][2][2];
long long ans;
inline void pushup(int root) {
    tree[root][0][1] = max(max(
        tree[root<<1][0][1]+tree[root<<1|1][0][1],
        tree[root<<1][0][0]+tree[root<<1|1][0][1]),
        tree[root<<1][0][0]+tree[root<<1|1][1][1]);
    tree[root][1][0] = max(max(
        tree[root<<1][1][0]+tree[root<<1|1][1][0],
        tree[root<<1][1][1]+tree[root<<1|1][0][0]),
        tree[root<<1][1][0]+tree[root<<1|1][0][0]);
    tree[root][0][0] = max(max(
        tree[root<<1][0][1]+tree[root<<1|1][0][0],
        tree[root<<1][0][0]+tree[root<<1|1][0][0]),
        tree[root<<1][0][0]+tree[root<<1|1][1][0]);
    tree[root][1][1] = max(max(
        tree[root<<1][1][1]+tree[root<<1|1][0][1],
        tree[root<<1][1][0]+tree[root<<1|1][1][1]),
        tree[root<<1][1][0]+tree[root<<1|1][0][1]);
}
inline void build(int l,int r,int root) {
    if (l == r) {
        scanf("%d",&tree[root][1][1]);
        return;
    }
    int mid = l+r>>1;
    build(l,mid,root<<1);
    build(mid+1,r,root<<1|1);
    pushup(root);
}
inline void update(int l,int r,int num,int x,int root) {
    if (l > num || r < num) return;
    if (l == r) {
        tree[root][1][1] = x;
        return;
    }
    int mid = l+r>>1;
    update(l,mid,num,x,root<<1);
    update(mid+1,r,num,x,root<<1|1);
    pushup(root);
}
int main() {
//  freopen("luogu3097.in","r",stdin);
//  freopen("luogu3097.out","w",stdout);
    scanf("%d%d",&n,&d);
    build(1,n,1);
    for (int i = 1,x,y;i <= d;i++) {
        scanf("%d%d",&x,&y);
        update(1,n,x,y,1);
        ans += max(max(tree[1][0][1],tree[1][1][0]),max(tree[1][1][1],tree[1][0][0]));
    }
    printf("%lld",ans);
    return 0;
}

【USACO13DEC】 最优挤奶 - 线段树

原文：https://www.cnblogs.com/lrj124/p/11813193.html