A182174.Yuilice 的环形货架

普及+/提高

官方

通过率:0%

时间限制:3.00s

内存限制:256MB

题目描述

Yuilice 把相同的收纳盒放在一圈货架上。货架按顺时针顺序编号为 1,2,…,n1,2,\ldots,n,其中 nn 号的下一个是 11 号。

第 ii 个货架最初有 aia_i 个盒子,希望最终恰有 bib_i 个。保证盒子的初始总数与目标总数相等。

对每个 ii,把 ii 号货架的下一个货架记为 jj。可以进行以下任意次操作:

  • 若 ii 号货架有盒子,花费 cic_i,把其中一个盒子移到 jj 号货架;
  • 若 jj 号货架有盒子,花费 did_i,把其中一个盒子移到 ii 号货架。

每条相邻通道还有一次性开通费 eie_i:只要曾通过该通道移动过盒子,就额外支付一次 eie_i,不区分方向;完全没有使用的通道不收费。

每次操作只移动一个盒子;货架容量没有上限,途中可以暂存盒子。请计算达到目标状态所需的最小总费用,包括移动费用和通道开通费。

输入格式

第一行包含一个整数 nn,表示货架数量。

第二行包含 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n,其中 aia_i 表示第 ii 个货架最初的盒子数。

第三行包含 nn 个整数 b1,b2,…,bnb_1,b_2,\ldots,b_n,其中 bib_i 表示第 ii 个货架的目标盒子数。

接下来 nn 行,第 ii 行包含三个整数 ci,di,eic_i,d_i,e_i,分别表示沿第 ii 条相邻通道顺时针、逆时针移动一个盒子的费用,以及该通道的一次性开通费;第 nn 条通道连接 nn 号与 11 号货架。

输出格式

输出一行一个整数,表示最小总费用。

输入输出样例

  • 输入#1

    4
    3 0 0 1
    0 2 2 0
    1 4 2
    5 1 9
    1 4 1
    2 1 3
    

    输出#1

    17
    

说明/提示

样例解释

将 11 号货架的两个盒子分别移到 22 号,共花费 22。

将 11 号货架剩下的一个盒子逆时针移到 44 号,花费 11。此时 44 号有两个盒子,再将它们分别逆时针移到 33 号,共花费 88。

最终盒子数为 0,2,2,00,2,2,0,移动费用为 2+1+8=112+1+8=11。使用了第 1,3,41,3,4 条通道,开通费为 2+1+3=62+1+3=6,总费用为 1717,这是最小值。

数据范围

对于所有测试数据,满足 3≤n≤2×1053\le n\le2\times10^5,0≤ai,bi≤1040\le a_i,b_i\le10^4,1≤ci,di≤1031\le c_i,d_i\le10^3,0≤ei≤1090\le e_i\le10^9,∑i=1nai=∑i=1nbi\sum_{i=1}^n a_i=\sum_{i=1}^n b_i。记 S=∑i=1naiS=\sum_{i=1}^n a_i,则 0≤S≤2×1090\le S\le2\times10^9。

测试点编号 nn SS
1∼41\sim4 3≤n≤63\le n\le6 0≤S≤60\le S\le6
5∼105\sim10 3≤n≤20003\le n\le2000 0≤S≤2×1070\le S\le2\times10^7
11∼2011\sim20 3≤n≤2×1053\le n\le2\times10^5 0≤S≤2×1090\le S\le2\times10^9

输入解题思路,AI测评打分。不知道怎么写?

首页