#P1389. 一个关于序列的游戏

一个关于序列的游戏

题目描述

有一个序列,你可以在上面删除符合要求的连续段若干次。每次删除都会得到连续段长度对应的分数。

需要符合的要求为:

  1. 相邻两个元素相差为 11
  2. 如果某个元素不在连续段的最左或最右,那么这个元素就不能同时小于相邻的左右两个元素。

[1,2,3,4,3],[1,2],[3,2],[3][1,2,3,4,3],[1,2],[3,2],[3] 都符合条件。

显然,删除掉连续段后,这个段的左边和右边并在一起成为相邻元素。

你的任务是对于给出的序列,计算出可能获得的最大总分。

输入格式

第一行一个整数 NN,表示序列长度。

第二行 NN 个数,V1,V2VNV_1,V_2 \cdots V_N,代表每个长度对应的分数。

第三行 NN 个数,A1,A2ANA_1,A_2 \cdots A_N,代表初始序列的每个元素。

输出格式

一个数,可以获得的最大总分。

6
-100 5 6 10 0 0
3 1 2 3 4 10

11

提示

数据范围及约定

  • 对于 10%10\% 的数据 ,N3,N \le 3
  • 对于 40%40\% 的数据 ,N10,N \le 10
  • 对于 70%70\% 的数据 ,N70,N \le 70
  • 对于 100%100\% 的数据 ,1N150,1 \le N \le 15010000Vi10000-10000 \le V_i \le 100000Ai10000000000 \le A_i \le 1000000000。相同的 AiA_i 不会超过 1414 个。