LRU is Best? (Hard Version) - 题目

传统 1000 ms 1024 MiB

标准 IO

文本比较 dd

简单版和困难版的区别仅在于简单版对于数组 $x$ 、 $y$ 和 $z$ 有额外约束，在困难版中对于三个数组中的值没有额外约束。

有一个长度为 $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(1\le x_i\le 10^9)$ ，代表数组 $x$ 。

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

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

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

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

输入样例

14
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
2 2
1 2
9 9
1 2
8 1
5 2
1 2 2 2 1
8 2 4 5 9
6 8 3 1 8
5 5 3 2 6
6 2
1 2 3 4 5 1
3 2 8 4 9 5
3 0 2 1 9 8
1 2 9 0 8 3
10 3
1 2 3 2 1 4 1 2 4 3
5 9 8 1 5 7 9 8 7 1
5 5 6 1 2 8 7 2 1 0
9 0 0 0 2 7 9 6 9 6
10 5
1 6 1 5 5 9 7 7 8 8
10 14 14 16 8 7 17 2 6 5
6 1 7 9 9 0 5 9 0 2
4 4 6 5 6 4 3 8 0 8
10 2
3 7 1 6 3 10 4 3 1 2
9 2 1 4 3 6 7 1 1 8
0 0 0 0 0 0 0 0 0 0
3 7 4 2 2 0 1 4 7 3
10 1
1 2 1 2 1 2 1 2 1 1
1 1 1 1 1 1 1 1 1 1
0 1 0 1 0 1 0 1 0 0
1 0 0 0 0 0 0 0 0 0

输出样例

#557. LRU is Best? (Hard Version)

题目描述

输入格式

输出格式

样例