取数游戏2--牛客网

链接：https://ac.nowcoder.com/acm/problem/14701
来源：牛客网
 

题目描述

给定两个长度为n的整数列A和B，每次你可以从A数列的左端或右端取走一个数。假设第i次取走的数为ax，则第i次取走的数的价值vi=bi⋅ax，现在希望你求出∑vi的最大值。

输入描述:

第一行一个数T，表示有T组数据。
对于每组数据，第一行一个整数n，
接下来两行分别给出A数列与B数列。

输出描述:

每一组数据输出一行，最大的∑vi。

示例1

输入

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≤10^3

1≤ai,bi≤10^3

 

分析：

标签是动态规划。首先我们先考虑最小的情况：

 此时只有一个元素，那不用说了，直接做乘法。

 

接下来，我们考虑两个元素的情况。

 

 

可以看出，两个元素的话，有两种情况。

1.最开始选了左边，就只剩下右边一个元素的情况。

2.最开始选了右边，就只剩下左边一个元素的情况。

此时就开始有点动态规划的影子了。选左还是选右，这是个问题。

 

接下来，三个元素的情况。

 

 

 

 

此时很明显的动态规划了。三个元素也有两种情况：

1.最开始选了左边，还剩下右边两个元素的情况。

2.最开始选了右边，还剩下左边两个元素的情况。

 

 我们，以a[i]来表示A数列中的元素，以b[i]来表示B数列中的元素，以dp[i][j]来表示区间【i，j】的最优解。（即最大值）

接下来，我们就要开始写动态规划三要素了。

1.边界。即元素只有一个的时候，即dp[i][i]，此时dp[i][i]=a[i]*b[n-1]。因为你到最后面了，只剩下一个元素a[i]，而此时既然是最后时刻，那B数列肯定只剩下一个元素b[n-1]，直接相乘就是了。

2.最优子结构。我们以有三个元素为例子，尝试写一下最优子结构。

看上面的图片，两情况。

1.dp[0][3-1]=a[0]*b[0]+dp[1][3-1];

2.dp[0][3-1]=a[3-1]*b[0]+dp[0][1];

即dp[0][3-1]=max{a[0]*b[0]+dp[1][2],a[2]*b[0]+dp[0][1]};

3.状态转移方程：

dp[i][j]=max（a[i]*b[n-(j-i+1)]+ dp[i+1][j], a[j]*b[n-(j-i+1)]+dp[i][j-1]  ）;

(注：j-i+1表示区间【i，j】所含元素个数，即还剩下多少个，而n-（j-i+1）即代表此时是第几次取元素，该取B序列的那一个。)

AC代码：

 

#include<iostream>
#include<string.h>
#include <algorithm>
using namespace std;
int main()
{

	int T;
	cin>>T;
	while(T--)
	{
		int n;
		cin>>n;
		int a[n],b[n],dp[n][n];
		for(int i=0; i<n; i++)
		{
			cin>>a[i];
		}
		for(int i=0; i<n; i++)
		{
			cin>>b[i];
		}
		memset(dp,0,sizeof(dp));

		for(int i=0; i<n; i++)
		{
			dp[i][i]=a[i]*b[n-1];
		}

		for(int i=n-1;i>=0;i--)
		{
			for(int j=i+1; j<n; j++)
			{
				dp[i][j]=max(a[i]*b[n-(j-i+1)]+dp[i+1][j],a[j]*b[n-(j-i+1)]+dp[i][j-1]);
			}
		}
		
		
		cout<<dp[0][n-1]<<endl;

	}
	return 0;
}