← 返回题目

题库练习最佳挤奶

← 上一题下一题 →

A2217 | $最佳挤奶$

来源USACO / 2013

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

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

输入格式

* 第 1 行：N 和 D 的值。 * 第 2..1+N 行：第 i+1 行包含 M（i） 的初始值。 * 第 2+N 行。1+N+D：第 1+N+d 行包含两个整数 i 和 m， 表示 Farmer John 在 d 天开始时将 M（i） 的值更新为 m。

输出格式

* 第 1 行：FJ 在 D 天内可以产生的最大牛奶总量。

输入输出样例

输入 #1

输出 #1

C++ 编辑器

输入

输出