1.简述:
给定两个长度为 n 的整数列 A 和 B ,每次你可以从 A 数列的左端或右端取走一个数。假设第 i 次取走的数为 ,则第i次取走的数的价值
,现在希望你求出
的最大值。
数据范围: ,
第一行输入一个正整数 n ,表示数列 A 和 B 的长度。
第二行和第三行各输入 n 个正整数,分别表示数列 A 和 B 的元素
按题目要求输出最大值
输入:
2
1 1000
2 1
输出:
2001
输入:
5
1 3 5 2 4
1 2 3 4 5
输出:
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
2.代码实现:
import java.util.*;标签:yyds,int,取数,++,length,干货,new,dp,size From: https://blog.51cto.com/u_15488507/5893354
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int length = sc.nextInt();
int[] a = new int[length];
int[] b = new int[length];
int i = 0;
while (i < length) {
a[i] = sc.nextInt();
i++;
}
i = 0;
while (i < length) {
b[i] = sc.nextInt();
i++;
}
run(a, b);
}
public static void run(int[] a, int[] b) {
int size = a.length;
int[][] dp = new int[size + 1][size + 1];//dp[i][j]表示取a[i],b[j]时之前的和;
for (int x = 0; x < size; x++) {
dp[x][x] = a[x] * b[size - 1];
}
for (int i = 1; i <= size; i++) //枚举区间长度
{
for (int j = 0; j + i < size; j++) //枚举区间起点
{
int k = i + j; //区间终点
//当前区间可获得的最大价值
dp[j][k] = Math.max(dp[j + 1][k] + a[j] * b[size - 1 - i], dp[j][k - 1] + a[k] * b[size - 1 - i]);//取左面还是右面
}
}
System.out.println(dp[0][size - 1]);
}
}