P1389 A Game About a Sequence

There is a sequence. You may delete, any number of times, a contiguous segment that meets the rules below. Each deletion yields a score equal to the length of that segment. The segment must satisfy: 1. For every pair of adjacent elements, the absolute difference is $1$. 2. If an element is not the leftmost or rightmost element of the segment, then it cannot be strictly smaller than both of its immediate neighbors. All of $[1,2,3,4,3]$, $[1,2]$, $[3,2]$, and $[3]$ satisfy the rules. After removing a segment, the elements to the left and right of that segment become adjacent. Your task is: for the given sequence, compute the maximum possible total score.

The first line contains an integer $N$, the length of the sequence. The second line contains $N$ integers $V_1, V_2 \cdots V_N$, where $V_L$ is the score for deleting a segment of length $L$. The third line contains $N$ integers $A_1, A_2 \cdots A_N$, the elements of the initial sequence.

Output a single integer: the maximum total score that can be obtained.

### Constraints - For $10\%$ of the testdata, $N \le 3$. - For $40\%$ of the testdata, $N \le 10$. - For $70\%$ of the testdata, $N \le 70$. - For $100\%$ of the testdata, $1 \le N \le 150$, $-10000 \le V_i \le 10000$, $0 \le A_i \le 1000000000$. No value $A_i$ appears more than $14$ times. Translated by ChatGPT 5