取数游戏2(动态规划java)

取数游戏2

题目描述

给定两个长度为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

数据范围

对于100的数据,保证 T≤10,1≤n≤1000,1≤ai,bi≤1000。

算法思路

首先题目中说的是每次取A数列的左端或右端,而B数列取的是第i个元素,暴力解的思路肯定就是通过回溯算法,把所有的情况尝试出来,但是这种思路肯定是会超时的,所以采用优化的算法动态规划。
首先定义dp数组的意义,因为最后要求的是A数列和B数列得出的∑vi最大值,所以可以定义为dp[0][n-1]为A数列[0 ~ n-1]得出的∑vi最大值,而dp[i][j]表示的是A数列[i ~ j]计算出来的∑vi最大值。
按照这个思路继续,继续推断递推公式,因为题干中说的是每次从A数列左端或右端取走一个数,并且乘上B数列的第i个元素,我们可以反向操作,初始的时候A数列没有元素,每次在左端或右端添加一个数,并且乘上B数列的第n-i个元素,通过这种逆向思路变可以推断出递推公式,既然每次是在左端或右端添加数,对于dp[i][j]的值来说,可能是由于dp[i+1][j]添加左端的数并且乘上B数列对应的元素得到的,也可能是dp[i][j-1]乘上B数列对应的元素得到的,取两者的最大值,那么就可以得出递推公式是dp[i][j]=max(dp[i+1][j]+B[n-j+i-1]*A[i],dp[i][j-1]+B[n-j+i-1]*A[j]),其中B[n-j+i-1]是左端或者右端添加数对应的B数列元素。
那么最后就是开始遍历dp数组来算出每个值了,其中dp数组的初始化有一个规律,就是最开始取的A数列的元素一定是乘上B数列中的最后的元素,因为dp[i]j的时候代表的意义一定是只有一个数的时候,所以在初始化dp数组的时候,让dp对角线元素等于A数列对应的元素乘上B数列最后一个元素作为初始值。
在这里插入图片描述
如上图,按照题干的测试案例给出的每个数组的值,其中dp数组是按照下面的元素和左面的元素来推断出来的,最后dp[0][4]便是答案。

代码

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int T = scanner.nextInt();
        while (T>0){
            T-=1;
            //定义输入数据的初始化
            int n = scanner.nextInt();
            int []A = new int[n];
            int []B = new int[n];
            int [][]dp=new int[n][n];
            for(int i=0;i<n;++i){
                A[i]= scanner.nextInt();
            }
            for(int i=0;i<n;++i){
                B[i]= scanner.nextInt();
            }
            //让对角线上的元素等于B数组最后一个元素和A数组的第i个元素,动态规划的数组初始化
            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]=Math.max(dp[i+1][j]+B[n-j+i-1]*A[i],dp[i][j-1]+B[n-j+i-1]*A[j]);
                }
            }
            System.out.println(dp[0][n-1]);
        }
    }
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/163589.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【算法挨揍日记】day27——152. 乘积最大子数组、1567. 乘积为正数的最长子数组长度

152. 乘积最大子数组 152. 乘积最大子数组 题目描述&#xff1a; 给你一个整数数组 nums &#xff0c;请你找出数组中乘积最大的非空连续子数组&#xff08;该子数组中至少包含一个数字&#xff09;&#xff0c;并返回该子数组所对应的乘积。 测试用例的答案是一个 32-位 整…

【狂神说Java】Docker概述 | Docker安装 | Docker的常用命令

✅作者简介&#xff1a;CSDN内容合伙人、信息安全专业在校大学生&#x1f3c6; &#x1f525;系列专栏 &#xff1a;【狂神说Java】 &#x1f4c3;新人博主 &#xff1a;欢迎点赞收藏关注&#xff0c;会回访&#xff01; &#x1f4ac;舞台再大&#xff0c;你不上台&#xff0c…

PS学习笔记——视图调整

文章目录 图片拖动图片旋转图片缩放 视图只是我们在对图片进行操作时所看到的图片状态&#xff0c;并不会实际改变图片的属性。目的是方便我们在操作图片时有最舒服的体验 图片拖动 工具栏中有这样一个抓手工具(快捷键H)&#xff0c;选择这个抓手工具便可以在图片放大后能用鼠标…

2023年四川省安全员A证证模拟考试题库及四川省安全员A证理论考试试题

题库来源&#xff1a;安全生产模拟考试一点通公众号小程序 2023年四川省安全员A证证模拟考试题库及四川省安全员A证理论考试试题是由安全生产模拟考试一点通提供&#xff0c;四川省安全员A证证模拟考试题库是根据四川省安全员A证最新版教材&#xff0c;四川省安全员A证大纲整理…

BGP联盟和团体属性实验

目录 一、实验拓扑 二、实验要求 三、实验步骤 1、IP地址配置 2、ospf配置 3、BGP建邻 4、宣告网段 5、配置团体属性 一、实验拓扑 二、实验要求 1、按照图示配 IP 地址&#xff0c;R2&#xff0c;R3&#xff0c;R4&#xff0c;R5分别配 Loopbacke 口地址作为OSPF的Ro…

系列六、GC垃圾回收【四大垃圾算法-标记清除算法】

一、概述 标记清除算法分为两个阶段&#xff0c;即&#xff1a;标记和清除两个阶段&#xff0c;先标记出要回收的对象&#xff0c;然后统一回收这些对象。形如&#xff1a; 老年代一般是由标记清除或者标记清除 标记压缩的混合实现。 二、原理 用通俗的话解释一下标记清除算法…

深入解析:开发抖音酒店景区小程序的技术

抖音作为社交媒体平台的佼佼者&#xff0c;其独特的风格和用户基础吸引了无数开发者的目光。在本文中&#xff0c;我们将深入解析开发抖音酒店景区小程序的关键技术&#xff0c;为开发者提供实用指南。 1.抖音风格设计 在开发酒店景区小程序时&#xff0c;首先要注重界面设计…

Leetcode—剑指Offer LCR 140.训练计划II【简单】

2023每日刷题&#xff08;三十三&#xff09; Leetcode—LCR 140.训练计划II 实现代码 /*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/ struct ListNode* trainingPlan(struct ListNode* head, int cnt) {str…

C/C++ 获取主机网卡MAC地址

MAC地址&#xff08;Media Access Control address&#xff09;&#xff0c;又称为物理地址或硬件地址&#xff0c;是网络适配器&#xff08;网卡&#xff09;在制造时被分配的全球唯一的48位地址。这个地址是数据链路层&#xff08;OSI模型的第二层&#xff09;的一部分&#…

《向量数据库指南》——什么是 向量数据库Milvus Cloud的Range Search?

Range Search 功能诞生于社区。 某天,一位做系统推荐的用户在社区提出了需求,希望 Milvus Cloud 能提供一个新功能,可以返回向量距离在一定范围之内的结果。而这不是个例,开发者在做相似性查询时,经常需要对结果做二次过滤。 为了帮助用户解决这一问题,Milvus Cl…

STL的介绍

STL 是 C 标准模板库&#xff08;Standard Template Library&#xff09;的缩写&#xff0c;是 C 标准库中的一个重要组成部分。STL 提供了一组通用的模板类和函数&#xff0c;用于实现常用的数据结构和算法&#xff0c;如向量&#xff08;vector&#xff09;、链表&#xff08…

科大讯飞会议笔记本、GoodNotes、E人E本 功能及体验对比

科大讯飞会议笔记本、GoodNotes、E人E本功能及体验对比 【旧文档&#xff0c;怕失传】 通过对科大讯飞会议笔记本、基于iPad的GoodNotes以及E人E本的各项功能指标进行了实际对比&#xff0c;得出了以下结果&#xff1a; 在实际体验中&#xff0c;科大讯飞笔记本在录音方面表…

酷柚易汛ERP - 盘点操作指南

1、应用场景 盘点功能是定期或临期对库存货物进行清点&#xff0c;使账面记录与实际库存相符合&#xff0c;从而随时掌握货物盈亏状态。 2、主要操作 2.1 盘点商品查询 打开【仓库】-【盘点】新增盘点单&#xff0c;筛选需要盘点的日期范围、库存及相应商品 2.2 录入盘点数…

【算法挨揍日记】day30——300. 最长递增子序列、376. 摆动序列

300. 最长递增子序列 300. 最长递增子序列 题目解析&#xff1a; 给你一个整数数组 nums &#xff0c;找到其中最长严格递增子序列的长度。 子序列 是由数组派生而来的序列&#xff0c;删除&#xff08;或不删除&#xff09;数组中的元素而不改变其余元素的顺序。例如&#…

文件隐藏 [极客大挑战 2019]Secret File1

打开题目 查看源代码发现有一个可疑的php 访问一下看看 点一下secret 得到如下页面 响应时间太短我们根本看不清什么东西&#xff0c;那我们尝试bp抓包一下看看 提示有个secr3t.php 访问一下 得到 我们看见了flag.php 访问一下可是什么都没有 那我们就进行代码审计 $file$_…

Redis篇---第七篇

系列文章目录 文章目录 系列文章目录前言一、是否使用过 Redis Cluster 集群,集群的原理是什么?二、 Redis Cluster 集群方案什么情况下会导致整个集群不可用?三、Redis 集群架构模式有哪几种?前言 前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分…

hive sql 行列转换 开窗函数 炸裂函数

hive sql 行列转换 开窗函数 炸裂函数 准备原始数据集 学生表 student.csv 讲师表 teacher.csv 课程表 course.csv 分数表 score.csv 员工表 emp.csv 雇员表 employee.csv 电影表 movie.txt 学生表 student.csv 001,彭于晏,1995-05-16,男 002,胡歌,1994-03-20,男 003,周杰伦,…

架构分四层,我的系统为什么越来越乱

上一期我们学习了&#xff0c;一个应用架构的四层及职责。但是&#xff0c;随着业务需求的增多&#xff0c;时间的推移&#xff0c;系统架构慢慢的就变乱了。 本文视频语音版本&#xff1a; 我们这期来分析是什么原因导致的。你说是因为“熵增”&#xff0c;这是肯定的。但熵增…

【C语言的秘密】密探—深究C语言中多组输入的秘密!

场景引入&#xff1a; 你是否在刷题过程中&#xff0c;经常遇到以下场景呢&#xff1f; 场景一&#xff1a; 场景二&#xff1a; 从这些题上都能看见输入描述中提出了一条多组输入&#xff0c;那啥是多组输入&#xff1f;如何实现它呢&#xff1f; 多组输入&#xff1a;在输入…

【腾讯云云上实验室-向量数据库】探索腾讯云向量数据库:全方位管理与高效利用多维向量数据的引领者

目录 前言1 腾讯云向量数据库介绍2 向量数据库信息及设置2.1 向量数据库实例信息2.2 实例监控2.3 密钥管理2.4 安全组2.5 Embedding2.6 可视化界面 3 可视化界面4 Embedding4.1 embedding_coll精确查询4.2 unenabled_embedding_coll精确查询 5 数据库5.1 创建数据库5.2 插入数据…
最新文章