← 返回题目列表

Codeforces · 1859/E

E. 最大单调性

中文机器翻译题面 查看原题

给定一个长度为 $$$n$$$ 的数组 $$$a$$$ 和一个长度为 $$$n$$$ 的数组 $$$b$$$。段 $$$[l, r]$$$, $$$1 \le l \le r \le n$$$ 的成本定义为 $$$|b_l - a_r| + |b_r - a_l|$$$。

回想一下,如果满足以下条件之一,则两条线段 $$$[l_1, r_1]$$$、$$$1 \le l_1 \le r_1 \le n$$$ 和 $$$[l_2, r_2]$$$、$$$1 \le l_2 \le r_2 \le n$$$ 是不相交的: $$$r_1 < l_2$$$ 或 $$$r_2 < l_1$$$。

段 $$$[l, r]$$$, $$$1 \le l \le r \le n$$$ 的长度定义为 $$$r - l + 1$$$。

求非相交线段 $$$[l_j, r_j]$$$, $$$1 \le l_j \le r_j \le n$$$ 的最大可能成本总和,其总长度等于 $$$k$$$。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ $$$(1 \le t \le 1000)$$$ — 输入数据的组数。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le k \le n \le 3000$$$) — 数组 $$$a$$$ 的长度和段的总长度。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$) — 数组 $$$a$$$ 的元素。

每个测试用例的第三行包含 $$$n$$$ 整数 $$$b_1, b_2, \ldots, b_n$$$ ($$$-10^9 \le b_i \le 10^9$$$) — 数组 $$$b$$$ 的元素。

保证所有测试用例的$$$n$$$总和不超过$$$3000$$$。

输出

对于每个测试用例,输出一个数字 - 这些段的最大可能成本总和。

示例

输入 #1

5
4 4
1 1 1 1
1 1 1 1
3 2
1 3 2
5 2 3
5 1
1 2 3 4 5
1 2 3 4 5
7 2
1 3 7 6 4 7 2
1 5 3 2 7 4 5
4 2
17 3 5 8
16 2 5 9

输出 #1

0
10
0
16
28

注意

在第一个测试用例中,任何段的成本都是 $$$0$$$,因此总成本是 $$$0$$$。

在第二个测试用例中,我们可以采用成本为 $$$8$$$ 的段 $$$[1, 1]$$$ 和成本为 $$$2$$$ 的段 $$$[3, 3]$$$ 来获得总和 $$$10$$$。可以证明这是最优解。

在第三个测试用例中,我们只对长度为 $$$1$$$ 的段感兴趣,并且任何此类段的成本为 $$$0$$$。

在第四个测试用例中,可以证明最优总和是$$$16$$$。例如,我们可以采用段 $$$[3, 3]$$$ 和 $$$[4, 4]$$$。