A16537. Niko's Tactical Cards
编程题
普及-
知识点
题目描述
Niko 正在玩一个游戏。她的分数用一个整数 $k$ 表示，初始值为 $0$。
游戏有 $n$ 回合。在第 $i$ 回合，Niko 会获得一张红牌，上面写着整数 $a_i$，以及一张蓝牌，上面写着整数 $b_i$。她必须从中选择恰好一张，并根据选择更新她的分数：
- 如果她选择红牌，她的分数变为 $k - a_i$，其中 $k$ 为本回合之前的分数。
- 如果她选择蓝牌，她的分数变为 $b_i - k$，其中 $k$ 为本回合之前的分数。
随后游戏进入下一回合，或者如果已进行到第 $n$ 回合则游戏结束。
你的任务是求出 Niko 最终可能获得的最大分数。
游戏有 $n$ 回合。在第 $i$ 回合，Niko 会获得一张红牌，上面写着整数 $a_i$，以及一张蓝牌，上面写着整数 $b_i$。她必须从中选择恰好一张，并根据选择更新她的分数：
- 如果她选择红牌，她的分数变为 $k - a_i$，其中 $k$ 为本回合之前的分数。
- 如果她选择蓝牌，她的分数变为 $b_i - k$，其中 $k$ 为本回合之前的分数。
随后游戏进入下一回合，或者如果已进行到第 $n$ 回合则游戏结束。
你的任务是求出 Niko 最终可能获得的最大分数。
输入格式
每个测试用例包含多组数据。第一行包含测试用例个数 $t$（$1 \le t \le 10^3$）。接下来是每个测试用例的描述。
每个测试用例第一行包含一个整数 $n$（$1 \le n \le 10^5$），表示回合数。
第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$-10^9 \le a_i \le 10^9$）。
第三行包含 $n$ 个整数 $b_1, b_2, \ldots, b_n$（$-10^9 \le b_i \le 10^9$）。
保证所有测试用例中 $n$ 的总和不超过 $10^5$。
每个测试用例第一行包含一个整数 $n$（$1 \le n \le 10^5$），表示回合数。
第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$-10^9 \le a_i \le 10^9$）。
第三行包含 $n$ 个整数 $b_1, b_2, \ldots, b_n$（$-10^9 \le b_i \le 10^9$）。
保证所有测试用例中 $n$ 的总和不超过 $10^5$。
输出格式
对于每个测试用例，输出一个整数，表示 Niko 可能获得的最大分数。
输入输出样例
输入 #1
3 3 4 -8 -1 -3 -7 0 5 -3 1 0 7 1 -5 3 -1 4 -5 5 -7 7 5 4 9 -9 -3 3 2 2
输出 #1
6 12 27
说明/提示
在第一个测试用例中，一种最优策略如下：
| 回合 | 0 | 1 | 2 | 3 |
|------|---|-----|-----|-----|
| 选牌 | — | 蓝牌 | 红牌 | 红牌 |
| 分数 | 0 | $-3 - 0 = -3$ | $-3 - (-8) = 5$ | $5 - (-1) = 6$ |
在第二个测试用例中，一种最优策略如下：
| 回合 | 0 | 1 | 2 | 3 | 4 | 5 |
|------|---|-----|-----|-----|-----|-----|
| 选牌 | — | 蓝牌 | 蓝牌 | 蓝牌 | 蓝牌 | 红牌 |
| 分数 | 0 | $-5$ | 8 | $-9$ | 13 | 12 |
| 回合 | 0 | 1 | 2 | 3 |
|------|---|-----|-----|-----|
| 选牌 | — | 蓝牌 | 红牌 | 红牌 |
| 分数 | 0 | $-3 - 0 = -3$ | $-3 - (-8) = 5$ | $5 - (-1) = 6$ |
在第二个测试用例中，一种最优策略如下：
| 回合 | 0 | 1 | 2 | 3 | 4 | 5 |
|------|---|-----|-----|-----|-----|-----|
| 选牌 | — | 蓝牌 | 蓝牌 | 蓝牌 | 蓝牌 | 红牌 |
| 分数 | 0 | $-5$ | 8 | $-9$ | 13 | 12 |