P5774-[JSOI2016]病毒感染

题目:

题目描述:

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

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

一开始在 $i$ 号小镇，有 $a_i$ 名患者感染了 Jebola 病毒。

每一天 JYY 可以选择：

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

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

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

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

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

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

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

比如，如果 JYY 有如下行程：

第一天：从村庄 $1$ 前往村庄 $2$；

第二天：从村庄 $2$ 前往村庄 $3$；

第三天：治愈村庄 $3$；

第四天：前往村庄 $2$。

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

第五天：治愈村庄 $2$；

第六天：前往村庄 $1$；

第七天：治愈村庄 $1$。

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

输入格式:

输入第一行包含一个正整数 $N$；

接下来一行包含 $N$ 个整数，分别为 $a_1,a_2,…,a_N$。

输出格式:

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

样例:

样例输入 1:

1
2

6
40 200 1 300 2 10

样例输出 1:

1

1950

思路:

实现:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

#include "ybwhead/ios.h"
long long n, dp[3005][3005], dp2[3005], sum[3005], a[3005];
int main()
{
    yin >> n;
    for (long long i = 1; i <= n; ++i)
        yin >> a[i], sum[i] = sum[i - 1] + a[i];
    for (long long i = 1; i <= n - 1; ++i)
        for (long long j = 1; j <= n - i; ++j)
            dp[j][i + j] = dp[j + 1][i + j] + min((sum[i + j] - sum[j]) * 2, a[j] * i * 3 + sum[i + j] - sum[j]);
    memset(dp2, 0x3f, sizeof dp2);
    dp2[0] = 0;
    for (long long i = 1; i <= n; ++i)
        for (long long j = 0; j < i; ++j)
            dp2[i] = min(dp2[i], dp2[j] + dp[j + 1][i] + (4 * i - 4 * j - 2) * (sum[n] - sum[i]));
    printf("%lld", dp2[n]);
    return 0;
}