P10627 [JOI Open 2024] 中暑 / Heat Stroke

JOI 岛由 $L$ 个区组成，从西到东依次编号为 $1$ 到 $L$。岛上有 $(L-1)$ 条路，编号为 $1$ 到 $L-1$。第 $i$ 条路（$1\le i\le L-1$）双向连接着区 $i$ 和区 $i+1$。 现在，IOI 20XX 计划在 JOI 岛上举行！然而，令人担心的是，JOI 岛以其“火炉”称号而闻名于世。在岛上中暑风险较高，尤其是对于不适应 JOI 岛炎热气候的外国人。所以，IOI 的组织者决定采取以下措施： - 对于每一个 $1\le i\le L$，在区 $i$ 上有一个容量为 $C_i$ 人的医院。注意，$C_i$ 可以为 $0$。 - 在 IOI 活动中，当有人在第 $x$ 条路（$1\le x\le L-1$）上中暑时，中暑者将以以下的程序送医： - 将中暑者送往区 $x$ 或者区 $x+1$ 上的未满员的医院。如果两个区上的医院都未满员，则送往哪一个医院都可以。如果两个医院都满员了，用直升机将中暑者送往岛外的医院。 由于动用直升机花销不小，组织者们想要估计可能的需要动用直升机的病人数量的**最大值**。他们考虑如下的情境： - 在 IOI 活动之前，医院中没有病人； - 在 IOI 活动中，有 $N$ 个人会依次中暑。第 $j$ 个（$1\le j\le N$）人在第 $X_j$ 条路上中暑； - 对于任意 $1\le j\le N-1$，当第 $(j+1)$ 个人中暑时，第 $1,2,\cdots,j$ 个人已经送达医院。由于中暑症状较为严重，在 IOI 活动中无人出院。 你需要写一个程序。给定区的数量，医院的信息和中暑者的信息，在上述情境下，计算可能的需要动用直升机的病人数量的最大值。

输入格式如下所示： > $L$\ > $C_1$ $C_2$ $\cdots$ $C_L$ \ > $N$\ > $X_1$ $X_2$ $\cdots$ $X_N$

输出一行一个数，即可能的需要动用直升机的病人数量的最大值。

### 样例解释 对于样例 $1$，考虑如下的情况： - 将第一个中暑者送往区 $2$ 上的医院。此时，三个区上的医院的病人数量分别为 $0,1,0$； - 将第二个中暑者送往区 $3$ 上的医院。此时，三个区上的医院的病人数量分别为 $0,1,1$； - 对于第三个中暑者，由于区 $2,3$ 上的医院均已满员，所以只能用直升机送出岛。 此时共有 $1$ 人动用直升机送出岛。可以证明这是最大值。 对于样例 $2$，考虑如下的情况： - 将第一个中暑者送往区 $2$ 上的医院。此时，六个区上的医院的病人数量分别为 $0,1,0,0,0,0$； - 将第二个中暑者送往区 $4$ 上的医院。此时，六个区上的医院的病人数量分别为 $0,1,0,1,0,0$； - 将第三个中暑者送往区 $5$ 上的医院。此时，六个区上的医院的病人数量分别为 $0,1,0,1,1,0$； - 对于第四个中暑者，由于区 $4,5$ 上的医院均已满员，所以只能用直升机送出岛。 - 将第五个中暑者送往区 $3$ 上的医院。此时，六个区上的医院的病人数量分别为 $0,1,1,1,1,0$； - 对于第六个中暑者，由于区 $2,3$ 上的医院均已满员，所以只能用直升机送出岛。 - 对于第七个中暑者，由于区 $3,4$ 上的医院均已满员，所以只能用直升机送出岛。 此时共有 $3$ 人动用直升机送出岛。可以证明这是最大值。 样例 $1$ 满足子任务 $1\sim 8$ 的条件。 样例 $2$ 满足子任务 $2\sim 8$ 的条件。 样例 $3$ 满足子任务 $1,5\sim 8$ 的条件。 样例 $4,5$ 满足子任务 $5\sim 8$ 的条件。 ### 数据范围 - $2 \le L \le 8\,000$； - $0 \le C_i \le 8\,000$（$1 \le i \le L$）； - $1 \le N \le 8\,000$； - $1 \le X_j \le L − 1$（$1 \le j \le N$）； - 输入数字全为整数。 【子任务】 1. （$6 $ points）$X_1 \le X_2 \le\cdots\le X_N$； 2. （$7 $ points）$L \le 18, N \le 18, C_i = 1 $（$1 \le i \le L$）； 3. （$7 $ points）$L \le 18, N \le 100, C_i = 1 $（$1 \le i \le L$）； 4. （$25$ points）$L \le 100, N \le 100, C_i = 1$ （$1 \le i \le L$）； 5. （$25$ points）$L \le 100, N \le 100$； 6. （$10$ points）$L \le 600, N \le 600$； 7. （$15$ points）$L \le 3\,500, N \le 3\,500$； 8. （$5 $ points）无额外约束。 由 Starrykiller 根据英文题面翻译。