Landscaping

题目描述

农夫约翰正在建造一个景观优美的花园，在此过程中需要搬运大量泥土。 花园由一列 $N$ 个花坛组成（$1 \leq N \leq 100,000$），其中花坛 $i$ 起初包含 $A_i$ 单位的泥土。农夫约翰希望重新布置花园，使得每个花坛 $i$ 最终包含 $B_i$ 单位的泥土。$A_i$ 与 $B_i$ 均为 $0 \ldots 10$ 范围内的整数。 为了完成景观改造，农夫约翰有若干选择：他可以花费 $X$ 单位金钱购买 1 单位泥土，并将其放入任意一个花坛中；他也可以从任意一个花坛中移除 1 单位泥土并运走，花费 $Y$ 单位金钱；他还可以将 1 单位泥土从花坛 $i$ 运送到花坛 $j$，花费为 $Z$ 乘以 $|i-j|$。请计算农夫约翰完成景观改造所需的最小总花费。

输入格式

第一行输入包含 $N$, $X$, $Y$, 和 $Z$ ($0 \leq X, Y \le 10^8; 0 \le Z \leq 1000$)。第 $i+1$ 行包含整数 $A_i$ 和 $B_i$。

输出格式

请输出农夫约翰用于景观改造所需支付的最小总费用。

4 100 200 1
1 4
2 3
3 2
4 0

210

提示

注意，本题曾在之前的 USACO 比赛中以银组难度出现；然而当前版本的限制大幅提高，因此不应期望仅靠之前那个更简单版本的解法获得很多分数。 题目来源：Brian Dean

标签: USACO|2016|Platinum

来源

USACO|2016|Platinum