题目理解

• 有 $N$ 个小镇在一条直线上，编号 $1 \dots N$，JYY 从 $1$ 出发。

• 每个小镇 $i$ 初始有 $a_i$ 个患者。

• 每天 JYY 可以：

  1. 治愈当前村庄的所有患者（这一天该村无人死亡）。
  2. 移动到相邻村庄。

• 如果某天开始时村庄 $i$ 有 $k$ 个患者（且未被治愈），那么当天结束时会死亡 $k$ 人（即患者数翻倍前死亡 $k$ 人？实际上是：每天患者会感染 $k$ 个健康村民并死去，所以每天死亡 $a_i$ 人，因为初始患者数固定为 $a_i$，直到被治愈）。

  注意：死亡人数是按天算的，每天每个未治愈的村庄固定死 $a_i$ 人，不是按当前患者数翻倍，而是每天固定死 $a_i$ 人（因为题目说“对于 i 号村庄，只要这个村庄没有被 JYY 彻底消灭疫情，那么每一天都会有 a_i 个村民死去”）。这意味着每个村庄的死亡人数只取决于它被治愈的时间（从开始到治愈的那一天数）。

• 行程限制：如果 JYY 经过某个村庄 $i$ 但没治愈，之后如果 JYY 从 $j$ 到 $k$ 且 $|k-i| < |k-j|$（即朝 $i$ 的方向走了一步），那么之后必须一直朝 $i$ 走直到治愈 $i$，中途可以治愈经过的村庄。

问题转化

我们要安排 JYY 的行程，使得所有村庄都被治愈，并且总死亡人数最少。

总死亡人数 = $\sum_{i=1}^N a_i \times t_i$，其中 $t_i$ 是村庄 $i$ 从开始到被治愈所经过的天数（不包括治愈当天，因为治愈当天无人死亡）。

更准确地说：

• 村庄 $i$ 在第 $d_i$ 天被治愈。
• 那么它会在第 $1, 2, \dots, d_i-1$ 天每天死 $a_i$ 人。
• 所以总死亡人数 = $\sum_{i=1}^N a_i \times (d_i - 1)$。

目标是最小化 $\sum a_i (d_i - 1)$。

行程限制的影响

限制条件意味着：一旦 JYY 在某个村庄 $i$ 未治愈并离开，之后如果朝 $i$ 的方向走了一步，就必须连续走到 $i$ 并治愈它，中途不能改变方向。

这实际上是一种“承诺”机制：不能给村民希望又让他们失望。

动态规划思路

这是一个区间 DP 问题。

设 $dp[l][r][0/1]$ 表示治愈区间 $[l, r]$ 的所有村庄，并且最后 JYY 停在左端点 $l$（0）或右端点 $r$（1）时，该区间内的村庄产生的最小死亡代价（只考虑这些村庄的死亡天数，但天数计算要考虑全局时间）。

但是天数与访问顺序有关，我们需要知道在治愈这个区间之前已经过了多少天，因为死亡是按天累积的。

更好的状态设计（常见于这类“关灯”、“治病”问题）：

• 设 $dp[l][r]$ 表示治愈区间 $[l, r]$ 的所有村庄，并且此时其它未治愈的村庄已经产生的死亡天数 = 区间长度）。

已知经典模型：在一条直线上从起点 $1$ 出发，要处理所有村庄，可以设计： $f[l][r][0/1]$ 表示已经治愈 $[l, r]$，当前在 $l(0)$ 或 $r(1)$，从开始到此刻的总死亡人数。

转移时，考虑从 $[l, r]$ 扩展到 $l-1$ 或 $r+1$，新治愈的村庄的死亡天数 = 当前已用天数 + 移动时间。

初始化：$f[1][1][0] = 0$（治愈村庄 1 在第 1 天，死亡 0）。

但这里起点固定为 1，所以 $l \le 1 \le r$ 才可能。

更精确地，我们令 $dp[l][r][0]$ 表示当前在 $l$，已经治愈了 $[l, r]$ 区间，所花费的总死亡代价。
$dp[l][r][1]$ 表示当前在 $r$，已经治愈了 $[l, r]$ 区间。

转移：

• 从 $dp[l][r][0]$ 可以走到 $l-1$，花费 1 天，此时所有未治愈的村庄（即 $[1..l-1] \cup [r+1..N]$）都会产生 $a_{l-1} + \sum_{其他未治愈} a_k$ 的死亡？不，是所有未治愈村庄的 $a$ 之和，因为每个未治愈村庄死 $a_i$ 人/天。

设 $S = \sum_{i=1}^N a_i$，$s[l][r] = \sum_{i=l}^r a_i$。

那么未治愈的村庄的 $a$ 之和 = $S - s[l][r]$。

所以： 从 $dp[l][r][0]$ 到 $l-1$： $dp[l-1][r][0] = \min(\dots, dp[l][r][0] + (S - s[l][r]))$，因为移动一天，所有未治愈村庄死 $S - s[l][r]$ 人。

从 $dp[l][r][0]$ 到 $r+1$（不可能，因为 $[l, r]$ 已治愈，$r+1$ 未治愈，但当前在 $l$，要去 $r+1$ 必须经过 $r$，但 $r$ 已治愈，所以可以直接扩展？实际上要检查限制条件）。

限制条件在 DP 中自动满足，因为我们不会在未治愈的村庄上“掉头”而不立即治愈它——我们的状态是连续治愈的区间，所以不会出现未治愈的村庄在区间内部的情况。

因此，这实际上就是经典的“关灯”问题（POJ 1222 扩展），在一条链上，起点固定，每次移动一天，每天所有未关的灯会产生代价，求最小总代价。

最终算法

状态：$dp[l][r][0/1]$ 表示治愈了区间 $[l, r]$，当前在 $l$（0）或 $r$（1），所花费的最小总死亡代价。

转移：

• $dp[l][r][0]$ 可以从 $dp[l+1][r][0] + (S - s[l+1][r]) \times (pos_{l+1} - pos_l)$ 转移（移动时间 = 距离，因为相邻村庄距离 1）。 也可以从 $dp[l+1][r][1] + (S - s[l+1][r]) \times (pos_r - pos_l)$ 转移。
• $dp[l][r][1]$ 可以从 $dp[l][r-1][1] + (S - s[l][r-1]) \times (pos_r - pos_{r-1})$ 转移， 也可以从 $dp[l][r-1][0] + (S - s[l][r-1]) \times (pos_r - pos_l)$ 转移。

初始化：$dp[1][1][0] = 0$。

答案：$\min(dp[1][N][0], dp[1][N][1])$。

注意：这里 $pos_i = i$（位置就是编号），所以 $pos_{i+1} - pos_i = 1$。

因此转移简化为：

$dp[l][r][0] = \min(dp[l+1][r][0] + (S - s[l+1][r]),\ dp[l+1][r][1] + (S - s[l+1][r]) \times (r - l))$

$dp[l][r][1] = \min(dp[l][r-1][1] + (S - s[l][r-1]),\ dp[l][r-1][0] + (S - s[l][r-1]) \times (r - l))$

其中 $s[l][r] = \sum_{k=l}^r a_k$，$S = s[1][N]$。

复杂度

$O(N^2)$，满足 $N \le 3000$。