8951: DP53 取数游戏
[Creator : ]
Description
给定两个长度为 n 的整数列 A 和 B ，每次你可以从 A 数列的左端或右端取走一个数。
假设第 i 次取走的数为 $A_x$，则第 i 次取走的数的价值 $v_i=b_i×a_x$。
现在希望你求出 $\sum_{i=1}^{n} v_i$ 的最大值。
Input
第一行输入一个正整数 n ，表示数列 A 和 B 的长度。
第二行和第三行各输入 n 个正整数，分别表示数列 A 和 B 的元素
Output
按题目要求输出最大值
Constraints
$1 \leq n \leq 1,000$
$1 \leq A_i,B_i \leq 1,000$
$1 \leq A_i,B_i \leq 1,000$
Sample 1 Input
2
1 1000
2 1
Sample 1 Output
2001
Sample 2 Input
5
1 3 5 2 4
1 2 3 4 5
Sample 2 Output
52
第一次从左边取走 $a_1,\ v_1=a_1⋅b_1=1$
第二次从左边取走 $a_2,\ v_2=a_2⋅b_2=6$
第三次从右边取走 $a_5,\ v_3=a_5⋅b_3=12$
第四次从右边取走 $a_4,\ v_4=a_4⋅b_4=8$
第五次取走剩下的 $a_3,\ v_5=a_3⋅b_5=25$
总价值 $\sum v_i=1+6+12+8+25=52$