#P5774. [JSOI2016] 病毒感染

[JSOI2016] 病毒感染

题目描述

JOSI 的边陲小镇爆发了严重的 Jebola 病毒疫情,大批群众感染生命垂危。计算机科学家 JYY 采用最新的算法紧急研制出了 Jebola 疫苗,并火速前往灾区救治患者。

一共有 NN 个小镇爆发了 Jebola 疫情。这些小镇由于地处边陲,仅仅通过一条长直公路连接。方便起见我们将这些小镇按照公路连接顺序由 11 编号到 NN。JYY 会在第一天一早抵达 11 号小镇。

一开始在 ii 号小镇,有 aia_i 名患者感染了 Jebola 病毒。

每一天 JYY 可以选择:

  1. 花费一天时间彻底治愈 JYY 目前所在的村庄的所有 Jebola 患者。这一天不会有任何患者死去;
  2. 花费一天的时间前往一个相邻的村庄。

当一天开始时,如果一个村庄里有 kk 个 Jebola 患者,那么这一天结束时,这 kk 个患者会感染另外 kk 个这个村子里的健康村民并死去。所以对于 ii 号村庄,只要这个村庄没有被 JYY 彻底消灭疫情,那么每一天都会有 aia_i 个村民死去。

JYY 希望采用措施使得疫情被整体消灭时,总共死去的村民数量尽量少。

为了达成这一目标,JYY 有时会选择抵达一个村庄但是并不对村民进行施救。这样的行为如果不加限制,往往会造成更加严重的后果。

试想这样的情形:假设当 JYY 第一次抵达村庄 ii,未作救治并直接前往了另一个村庄。那么由于 ii 村庄的人们求生心切,一旦当 JYY 朝向靠近 ii 村庄的方向前行时,ii 村庄的村民就会以为 JYY 是来救他们了,而产生巨大的期望。之后倘若 JYY 再次掉头朝着远离 ii 村庄的方向行进,那么 ii 村庄的村民就会因为巨大的失落而产生绝望的情绪。

为了避免这种情况,JYY 对他的行程做了如下规定:

假设 JYY 进入 ii 村庄并在第二天立即离开(村庄 ii 的疫情并未治愈)。如果在之后的某一天,JYY 从村庄 jj 前往村庄 kk,并满足 ki<kj|k-i| \lt |k-j|。那么在之后的日子里 JYY 只能朝着 ii 村庄前进直到抵达 ii 村庄并立即治愈该村的患者。在前往 ii 村庄的过程中,JYY 可以选择将途经村庄的疫情治愈。

比如,如果 JYY 有如下行程:

第一天:从村庄 11 前往村庄 22

第二天:从村庄 22 前往村庄 33

第三天:治愈村庄 33

第四天:前往村庄 22

此时 JYY 对于之后三天的行程只有唯一一种选择:

第五天:治愈村庄 22

第六天:前往村庄 11

第七天:治愈村庄 11

JYY 想知道在治愈所有村庄之前,至少会有多少村民因 Jebola 死去。

输入格式

输入第一行包含一个正整数 NN

接下来一行包含 NN 个整数,分别为 a1,a2,...,aNa_1,a_2,...,a_N

输出格式

输出一行一个整数,表示最优行程安排下会死去的村民数量。

6
40 200 1 300 2 10
1950

提示

样例说明

我们用 C(k)C(k) 表示治愈 kk 号村庄,iji \rightarrow j 表示从村庄 ii 前进到村庄 jj,用逗号分隔每一天的行程安排,那么样例中的最优策略为:

$1 \rightarrow 2 , C(2),2 \rightarrow 3 , 3 \rightarrow 4 , C(4) , 4 \rightarrow 3 , C(3) , 3 \rightarrow 2 , 2 \rightarrow 1 , C(1) , 1 \rightarrow 2 , 2 \rightarrow 3 , 3 \rightarrow 4 , 4 \rightarrow 5 , 5 \rightarrow 6 , C(6) , 6 \rightarrow 5 , C(5)$;

整个过程耗时 1818 天。


数据范围

对于 10%10\% 的数据,满足 N10N \le 10

对于 30%30\% 的数据,满足 N20N \le 20

对于 50%50\% 的数据,满足 N60N \le 60

对于 100%100\% 的数据,满足 1N30001 \le N \le 30001ai1091 \le a_i \le 10^9