#P9090. 「HNOI2021 省集 Day7」好

    ID: 5174 传统题 1000ms 256MiB 尝试: 4 已通过: 2 难度: 8 上传者: 标签>难度分类提高+/省选-构造与建模差分转化动态规划区间 DP枚举最后一次操作状态维度消除线性 DPCF2500区间及合并类DP

「HNOI2021 省集 Day7」好

题面描述

定义长度为 nn 的“好串”ss 满足:

$$\forall i\in[2,n],|s_i-s_{i-1}|=1\\\forall i\in[2,n-1],s_i\ge \frac{s_{i-1}+s_{i+1}}{2}$$

给你两个长度为 nn 的序列 a,va,v,每次选择一段“好”的、长度为 ii 的子串删掉,剩下的子串前后拼接,并获得 viv_i 的价值,不一定要删完。

求可能获得的最大价值。

输入格式

从标准输入读入。

第一行一个数 nn。

接下来一行 nn 个数 viv_i。

接下来一行 nn 个数 aia_i。

输出格式

输出到标准输出。

仅一行一个整数,表示可能获得的最大价值。

样例

样例 1

3
0 0 3
1 2 1
3

样例 2

6
1 4 5 6 7 1000
2 1 1 2 2 3
12

样例 3

见附加文件中 good2.in 与 good2.out。

数据范围

  • 对于 10%10\% 的数据,n≤5n\le 5,∣vi∣≤5|v_i|\le 5,ai≤5a_i\le 5。
  • 对于 30%30\% 的数据,n≤20n\le 20。
  • 对于另外 20%20\% 的数据,∣vi∣≤1|v_i|\le 1。
  • 对于 100%100\% 的数据,1≤n≤4001\le n\le 400,∣vi∣≤105|v_i|\le 10^5,1≤ai≤1091\le a_i\le 10^9。