5044. 宝箱

单点时限: 1.0 sec

内存限制: 256 MB

Cuber QQ 的《弈!悟!》一上线就成为了爆款手游。为了留住更多的活跃用户,Cuber QQ 准备设计一些奖励机制,吸引用户每天按时登陆游戏。

Cuber QQ 推出了一场 $n$ 天打卡活动,玩家每天登陆游戏就可获得一个红色宝箱和一个蓝色宝箱。红色宝箱和蓝色宝箱中均可开出一定数额的金币(金币数额一定是正整数)。而且随着连续打卡天数的增加,奖励会越加丰厚。在第 $i+1$ 天的红色宝箱中开出的金额一定高于第 $i$ 天的红色宝箱。同样地,第 $i+1$ 天的蓝色宝箱中开出的金额一定高于第 $i$ 天的蓝色宝箱。

核心玩家们肯定不会错过每一天的宝箱,一个全勤的玩家可以获得全部的 $2n$ 个宝箱。Cuber QQ 为了给玩家一点惊喜,他想,这所有的 $2n$ 个宝箱中的金币数应当互不相同;而且他想指定这其中某几个箱子一定会开出奇数数目的金币,其余的箱子一定会开出偶数数目的金币。

当然,Cuber QQ 也不想让玩家在一个箱子中获得太多的金币。他想问问你,在满足这些要求的前提下,如何安排每个宝箱开出的数额,可以使得一个玩家在单个宝箱中获得的金币的最大值尽可能小。

输入格式

第一行包含一个整数 $n$($1 \le n\le 1000$),表示登陆活动的天数。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_i$,$a_i=0$ 表示第 $i$ 天的红色宝箱一定开出偶数枚金币,$a_i=1$ 表示第 $i$ 天的红色宝箱一定会开出奇数枚金币。

第三行包含 $n$ 个整数 $b_1, b_2, \dots, b_i$,$b_i=0$ 表示第 $i$ 天的蓝色宝箱一定开出偶数枚金币,$b_i=1$ 表示第 $i$ 天的蓝色宝箱一定会开出奇数枚金币。

输出格式

输出共一行,包含一个整数,表示一个玩家在单个宝箱中获得的最多的金币数的最小值。

样例

Input
5
1 0 0 1 1
0 0 0 1 0
Output
12

提示

在样例所述的情况中,我们可以让每天的红色宝箱分别开出 1、2、4、5、7 枚金币,每天的蓝色宝箱分别开出 6、8、10、11、12 枚金币,这样玩家在单个宝箱中最多获得 12 个金币。在其他的方案中,玩家在单个宝箱中开出的金币数的最大值都不会小于 12。

180 人解决,469 人已尝试。

206 份提交通过,共有 1506 份提交。

4.8 EMB 奖励。

创建: 1 年前.

修改: 1 年前.

最后提交: 4 天,9 小时前.

来源: N/A

题目标签
DP