A182174.Yuilice 的环形货架
普及+/提高
通过率:0%
时间限制:3.00s
内存限制:256MB
题目描述
Yuilice 把相同的收纳盒放在一圈货架上。货架按顺时针顺序编号为 1,2,…,n,其中 n 号的下一个是 1 号。
第 i 个货架最初有 ai 个盒子,希望最终恰有 bi 个。保证盒子的初始总数与目标总数相等。
对每个 i,把 i 号货架的下一个货架记为 j。可以进行以下任意次操作:
- 若 i 号货架有盒子,花费 ci,把其中一个盒子移到 j 号货架;
- 若 j 号货架有盒子,花费 di,把其中一个盒子移到 i 号货架。
每条相邻通道还有一次性开通费 ei:只要曾通过该通道移动过盒子,就额外支付一次 ei,不区分方向;完全没有使用的通道不收费。
每次操作只移动一个盒子;货架容量没有上限,途中可以暂存盒子。请计算达到目标状态所需的最小总费用,包括移动费用和通道开通费。
输入格式
第一行包含一个整数 n,表示货架数量。
第二行包含 n 个整数 a1,a2,…,an,其中 ai 表示第 i 个货架最初的盒子数。
第三行包含 n 个整数 b1,b2,…,bn,其中 bi 表示第 i 个货架的目标盒子数。
接下来 n 行,第 i 行包含三个整数 ci,di,ei,分别表示沿第 i 条相邻通道顺时针、逆时针移动一个盒子的费用,以及该通道的一次性开通费;第 n 条通道连接 n 号与 1 号货架。
输出格式
输出一行一个整数,表示最小总费用。
输入输出样例
输入#1
4 3 0 0 1 0 2 2 0 1 4 2 5 1 9 1 4 1 2 1 3
输出#1
17
说明/提示
样例解释
将 1 号货架的两个盒子分别移到 2 号,共花费 2。
将 1 号货架剩下的一个盒子逆时针移到 4 号,花费 1。此时 4 号有两个盒子,再将它们分别逆时针移到 3 号,共花费 8。
最终盒子数为 0,2,2,0,移动费用为 2+1+8=11。使用了第 1,3,4 条通道,开通费为 2+1+3=6,总费用为 17,这是最小值。
数据范围
对于所有测试数据,满足 3≤n≤2×105,0≤ai,bi≤104,1≤ci,di≤103,0≤ei≤109,∑i=1nai=∑i=1nbi。记 S=∑i=1nai,则 0≤S≤2×109。
| 测试点编号 | n | S |
|---|---|---|
| 1∼4 | 3≤n≤6 | 0≤S≤6 |
| 5∼10 | 3≤n≤2000 | 0≤S≤2×107 |
| 11∼20 | 3≤n≤2×105 | 0≤S≤2×109 |
输入解题思路,AI测评打分。不知道怎么写?