-
题目描述:
给定两个长度为n的整数列A和B，每次你可以从A数列的左端或右端取走一个数。假设第i次取走的数为ax，则第i次取走的数的价值vi=bi⋅ax，现在希望你求出∑vi的最大值。
-
输入描述：
第一行一个数T，表示有T组数据。
对于每组数据，第一行一个整数n，
接下来两行分别给出A数列与B数列。 -
输出描述：
每一组数据输出一行，最大的∑vi。
-
示例：
输入
2
2
1 1000
2 1
5
1 3 5 2 4
1 2 3 4 5 -
输出
2001
52 - 说明
对于第二个样例，
第一次从左边取走a1，v1=a1⋅b1=1,
第二次从左边取走a2，v2=a2⋅b2=6,
第三次从右边取走a5，v3=a5⋅b3=12,
第四次从右边取走a4，v4=a4⋅b4=8,
第五次取走剩下的a3，v5=a3⋅b5=25。
总价值∑vi=1+6+12+8+25=52
备注：
T≤10
1≤n≤103
1≤ai,bi≤103
程序代码：(搜索)
#include<iostream>
#include<cstring>
#include<algorithm>
#include<set>
#define N 1200
using namespace std;
int a[N];
int b[N];
int dp[N][N];
int dfs(int l,int r,int t){
if(l>r) return 0;
if(dp[l][r]) return dp[l][r];
int temp=0;
temp=max(temp,dfs(l,r-1,t+1)+a[r]*b[t]);
temp=max(temp,dfs(l+1,r,t+1)+a[l]*b[t]);
return dp[l][r]=temp;
}
int main(){
int t;
cin>>t;
while(t--){
memset(dp,0,sizeof(dp));
int m;
cin>>m;
for(int i=0;i<m;i++)cin>>a[i];
for(int i=0;i<m;i++)cin>>b[i];
cout<<dfs(0,m-1,0)<<endl;
}
return 0;
}
