seuOJ556 - LRU is Best? (Easy Version)

• 题目类型：传统
• 输入文件：标准输入流
• 输出文件：标准输出流
• 时间限制：1000 ms
• 空间限制：1024 MiB
• 题目标签：夏季, 2025

题目描述

简单版和困难版的区别仅在于简单版对于数组 $x$、$y$ 和 $z$ 有额外约束，在简单版中所有的 $x_i=1$，所有的 $y_i=z_i=0$。

有一个长度为 $n$ 的数组 $a$ 和三个长度为 $n$ 的数组 $x,y,z$，$a$ 中的所有数字都是 $1$ 到 $n$ 的正整数。同时，还有一个长度为 $m(m\le n)$ 的数组 $b$，初始时数组 $b$ 中的所有元素都是 $0$。你的初始得分 $score$ 为 $0$。

你需要从左到右遍历数组 $a$，并且在你遍历到第 $i$ 个数字 $a_i$ 时：

• 假如数字 $a_i$ 在数组 $b$ 中，你的得分 $score$ 增加 $x_i$。
• 否则，你的得分 $score$ 扣除 $y_i$。接下来，你可以选择一个位置 $j(1\le j\le m)$，将数组 $b$ 中第 $j$ 个数字 $b_j$ 替换为 $a_i$ 并且使你的得分扣除 $z_i$（或者不进行替换操作）。

在遍历完所有数字后，你的得分 $score$ 的最大值是多少？

输入格式

第一行，一个整数 $t(1\le t\le 100)$，代表数据组数。

对于每组数据：

第一行，两个整数 $n,m(1\le m\le n\le 800)$，分别代表数组 $a$ 的长度和数组 $b$ 的长度。

第二行，$n$ 个整数 $a_1,\dots,a_n(1\le a_i\le n)$，代表数组 $a$。

第三行，$n$ 个整数 $x_1,\dots,x_n(x_i=1)$，代表数组 $x$。

第四行，$n$ 个整数 $y_1,\dots,y_n(y_i=0)$，代表数组 $y$。

第五行，$n$ 个整数 $z_1,\dots,z_n(z_i=0)$，代表数组 $z$。

保证同一测试点内 $n$ 的总和不超过 $800$。

输出格式

对于每组数据，输出一个整数 $score$，代表在最优替换方案下你的得分的最大值。

样例

输入样例

7
2 2
1 2
1 1
0 0
0 0
5 2
1 2 2 2 1
1 1 1 1 1
0 0 0 0 0
0 0 0 0 0
6 2
1 2 3 4 5 1
1 1 1 1 1 1
0 0 0 0 0 0
0 0 0 0 0 0
10 3
1 2 3 2 1 4 1 2 4 3
1 1 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
10 5
1 6 1 5 5 9 7 7 8 8
1 1 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
10 2
3 7 1 6 3 10 4 3 1 2
1 1 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
10 1
1 2 1 2 1 2 1 2 1 1
1 1 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0

输出样例

0
3
1
5
4
3
5