2971. 打气球(hard version)

【限制】1000ms, 256M

【问题描述】

你在玩一个打气球的游戏。你的面前有一排n个气球,第i个气球的权值为b[i](i=1~n),你的手里有一杆枪,枪里有n发子弹,第i发子弹有权值a[i](i=1~n)。由于你有强迫症,你每次打气球只会选择剩余气球的最左边或者最右边的那个打,据说是这样可以避免剩下的气球之间出现空隙。设第i发子弹打中的气球编号为c[i](1<=c[i]<=n),你在游戏中获得分数 P = Σ( a[i]*b[c[i]] )。请问在最好的情况下,你可以得到的最高分。

【输入形式】

输入一个T代表数据组数,T<=10

对于每组数据:
第一行一个整数 n(0<n<=2000)
第二行n个整数输入数组a的值
第三行n个整数输入数组b的值

(0<a[i]<40000, 0<b[i]<40000, i=1~n)

【输出形式】

对于每组数据,输出最高分Pmax

【样例输入】

2
1
24779 
1960 
4
1 2 3 4
1 2 3 4

【样例输出】

48566840
30





难度等级: 0
总通过次数: 4
总提交次数: 32