P12932 [NOISG 2020 Prelim] Visiting Singapore

新加坡每天都会举办一场活动，记 $Σ = \{1, 2, \ldots, K\}$ 表示所有可能的活动集合。参加第 $i$ 个活动可以让你的幸福值增加 $V[i]$。 假设连续 $n$ 天内举办的活动依次为 $S[1], S[2], \ldots, S[n]$（同一活动可能多次出现）。 你想依次参加 $m$ 个指定活动 $T[1], T[2], \ldots, T[m]$（同样可能重复）。因此，你计划选择某一天飞往新加坡，第 $i$ 天到达，第 $j$ 天离开。你也可以选择不去新加坡。 在新加坡停留期间，你尝试依次完成 $T[1]$ 至 $T[m]$ 的活动： - 成功参加第 $T[i]$ 个活动，幸福值增加 $V[T[i]]$； - 若跳过连续的 $T[p]$ 至 $T[q]$，幸福值减少 $A + (q - p + 1)B$； - 此外，在新加坡期间，若连续 $d$ 天未参加任何活动，幸福值减少 $A + dB$。更具体地说，若你仅在第 $p$ 天和第 $q$ 天参加了活动，且 $q \geq p + 2$，中间未参加任何活动，幸福值减少 $A + (q - p - 1)B$。 你想最大化自己的幸福值。请计算最大可能的幸福值。

第一行包含五个整数 $K, n, m, A, B$，含义如下： - $K$：活动种类数； - $n$：总天数； - $m$：目标活动数量； - $A, B$：负数，分别表示跳过惩罚参数。 第二行包含 $K$ 个正整数，第 $i$ 个整数表示第 $i$ 个活动带来的幸福值 $V[i]$。 第三行包含 $n$ 个整数，第 $i$ 个整数 $S[i]$ 表示第 $i$ 天举办的活动，范围 $1 \sim K$。 第四行包含 $m$ 个整数，第 $i$ 个整数 $T[i]$ 表示你计划依次参加的活动，范围 $1 \sim K$。

输出一行，表示在最优安排下可以获得的最大幸福值。

【样例解释】 对于样例 #1： 在这个例子中，$K = 1,\ n = 5,\ m = 3,\ A = -5,\ B = -4$。 由于只有一种类型的活动，且 $m \leq n$，一种可行的最优方案是第 $1$ 天去新加坡，第 $m$ 天离开。 由于每个活动的幸福值是 $10$，且 $m = 3$，所以最优幸福值是 $30$。 对于样例 #2： 由于只有一种类型的活动，且 $n > m$，一种可行的最优方案是第 $1$ 天去新加坡，第 $n$ 天离开。 同时，我们需要跳过 $T[m - n + 1]$ 到 $T[n]$ 这几个目标活动。 由于每个活动的幸福值是 $10$，$n = 3,\ m = 5$，因此前 $3$ 个目标活动可以尝试，获得幸福值 $10 \times 3 = 30$。 跳过最后 $2$ 个目标活动，幸福值减少 $A + 2B = -10 + 2(-5) = -20$。 因此，总幸福值是 $10$。 对于样例 #3： 最优方案是尝试第 $2$ 天的 $S[2] = 1$，第 $3$ 天的 $S[3] = 2$ 和第 $5$ 天的 $S[5] = 4$。 获得的幸福值是 $1 + 2 + 4 = 7$。 对于样例 #4： 最优方案是尝试第 $5$ 天的 $S[5] = 1$ 和第 $6$ 天的 $S[6] = 4$。 幸福值是 $1 + 4 - (2 \times 3) = -1$。 对于样例 #5： 最优方案是尝试第 $5$ 天的 $S[5] = 1$ 和第 $6$ 天的 $S[6] = 4$。 跳过 $T[2]$ 和 $T[3]$，幸福值减少 $-3$。 幸福值是 $1 + 4 - 3 = 2$。 对于样例 #6： 最优方案是在第 $2$ 天到达新加坡，第 $5$ 天离开。 该方案尝试了第 $2$ 天的 $S[2] = 1$，第 $3$ 天的 $S[3] = 5$ 和第 $5$ 天的 $S[5] = 6$。 我们跳过了 $T[2]$ 到 $T[4]$，因此幸福值减少 $-2 + 3 \times (-1) = -5$。 我们跳过了第 $4$ 天，幸福值减少 $-2 + (-1) = -3$。 幸福值是 $1 + 5 + 6 - 5 - 3 = 4$。 【数据范围】 - $1 \leq K \leq 1000$ - $1 \leq n, m \leq 5000$ - $-100 \leq A, B \leq 0$ - $1 \leq V[i] \leq 100$ | 子任务编号 | 分值 | 额外限制 | | :--------: | :--: | :--------------------------: | | $1$ | $4$ | $K = 1,\ m \leq n \leq 10^3$ | | $2$ | $6$ | $K = 1,\ n < m \leq 10^3$ | | $3$ | $12$ | $A = B = 0$ | | $4$ | $7$ | $A = 0$ | | $5$ | $8$ | $B = 0$ | | $6$ | $13$ | $n,\ m < 100$ | | $7$ | $50$ | 无额外限制 |