[JSOI2016]病毒感染[dp]

题意

\(n?\) 个村庄按标号排列,每个村庄有一个死亡速度 \(a_i?\) 表示每天死 \(a_i?\) 人(除非你治好这个村庄)。

你从 1 号村庄出发,每天可以选择向相邻的村庄进发或者治愈所在的村庄。

如果在这个过程中你的左边有未治愈的村庄,同时你向左走了一步,那么你需要把这些村庄全部治愈后才能接着自由行动。

求所有村庄都被治愈时最少的死亡人数。

\(n\le3000,a_i\le 10^9\)

分析

  • 如果一个村庄不及时救治,代价就是 \(|返回的位置 - pos| \times a_{pos}\) 。这启发我们枚举返回的位置。

  • 记录 \(a\) 的前缀和 \(s\) 定义状态 \(f_i\) 表示前 \(i\) 个村庄已经治愈,当前在 \(i\) 的最小代价。枚举返回位置 \(j\) ,容易得到:

    \[f_i=\min\{f_j+[j==0](s_n-s_j)+g_{j+1,i}+[i==n](i-j-1)(s_n-s_i)\}\]

    其中 \(g_{j,i}\) 表示从 \(j\) 走到 \(i\) ,然后走回 \(j?\) 的最小代价。

  • 枚举 \(j\) 是否在返回前治愈可以得到:

    \[g_{j,i}=g_{j+1,i}+\min\begin{cases}3a_j(i-j)+(s_n-s_j)+2(s_n-s_i)\\2(s_n-s_j)+(s_n-s_i)\end{cases}\]

    其中 \(g_{i,i}=(s_n-s_i)?\)

  • 这保证了在转移 \(f?\) 时,第一个走到的位置时返回后治愈的,如果不是,可以转化为此问题。

  • 时间复杂度 \(O(n^2)\)

代码

代码链接

相关文章