题目背景

2023 年 12 月 GESP C++ 七级编程第 2 题

题目描述

你和小杨玩纸牌游戏。双方每轮各出一张牌，牌面为 $0,1,2$，胜负规则为：$1$ 胜 $0$，$2$ 胜 $1$，$0$ 胜 $2$。第 $i$ 轮胜者得 $2a_i$ 分，败者不得分；若平局，双方各得 $a_i$ 分。

小杨会在游戏开始前公布全部 $N$ 轮出牌 $c_i$。你第 $1$ 轮可以任意出牌；从第 $2$ 轮开始，要么继续出上一轮的牌，要么记一次“换牌”并改出另一张牌。若整局共换牌 $t$ 次，结束时会额外扣除 $b_1+b_2+cdots+b_t$ 分。

请计算你最多能获得多少分。

输入格式

第一行输入整数 $N$。 第二行输入 $N$ 个非负整数 $a_1,a_2,ldots,a_N$。 第三行输入 $N-1$ 个非负整数 $b_1,b_2,ldots,b_{N-1}$。 第四行输入 $N$ 个整数 $c_1,c_2,ldots,c_N$，表示小杨每轮出的牌。

输出格式

输出一行一个整数，表示你最多能获得的分数。

4
1 2 10 100
1 100 1
1 1 2 0

219

6
3 7 2 8 9 4
1 3 9 27 81
0 1 2 1 2 0

56

数据范围与提示

• 对于 $30\%$ 的测试点，保证 $N\le 15$。
• 对于 $60\%$ 的测试点，保证 $N\le 100$。
• 对于全部测试点，保证 $1\le N\le 1000$，$0\le a_i,b_i\le 10^6$，$c_i\in\{0,1,2\}$。
• 样例 1 中最优策略可在第 $4$ 轮换牌，总分为 $20+200-1=219$。

来源

GESP 2023 年 12 月 C++ 七级 T2