【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】最优挤奶 - 线段树

题目描述

题意简述

思路

代码

最新文章

热门文章

巴特西

【USACO13DEC】 最优挤奶 - 线段树

题目描述

题意简述

思路

代码

最新文章

热门文章

【USACO13DEC】最优挤奶 - 线段树