作者微信
微

#yyds干货盘点# 动态规划专题：取数游戏

小技术 4个月前 (11-29) 0 999+

关注

1.简述：

描述

给定两个长度为 n 的整数列 A 和 B ，每次你可以从 A 数列的左端或右端取走一个数。假设第 i 次取走的数为 #yyds干货盘点# 动态规划专题：取数游戏，则第i次取走的数的价值，现在希望你求出的最大值。

数据范围： #yyds干货盘点# 动态规划专题：取数游戏 ,

输入描述：

第一行输入一个正整数 n ，表示数列 A 和 B 的长度。

第二行和第三行各输入 n 个正整数，分别表示数列 A 和 B 的元素

输出描述：

按题目要求输出最大值

示例1

输入：

2
1 1000
2 1

输出：

示例2

输入：

5
1 3 5 2 4
1 2 3 4 5

输出：

说明：

第一次从左边取走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.*;
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]);

        }

    }