LeetCode 5687.执行乘法运算的最大分数

news/2024/10/30 11:30:00/

题目描述

给你两个长度分别 n 和 m 的整数数组 nums 和 multipliers ,其中 n >= m ,数组下标 从 1 开始 计数。

初始时,你的分数为 0 。你需要执行恰好 m 步操作。在第 i 步操作(从 1 开始 计数)中,需要:

选择数组 nums 开头处或者末尾处 的整数 x 。
你获得 multipliers[i] * x 分,并累加到你的分数中。
将 x 从数组 nums 中移除。
在执行 m 步操作后,返回 最大 分数。

示例1

输入:nums = [1,2,3], multipliers = [3,2,1]
输出:14
解释:一种最优解决方案如下:
- 选择末尾处的整数 3 ,[1,2,3] ,得 3 * 3 = 9 分,累加到分数中。
- 选择末尾处的整数 2 ,[1,2] ,得 2 * 2 = 4 分,累加到分数中。
- 选择末尾处的整数 1 ,[1] ,得 1 * 1 = 1 分,累加到分数中。
总分数为 9 + 4 + 1 = 14 。

示例2

输入:nums = [-5,-3,-3,-2,7,1], multipliers = [-10,-5,3,4,6]
输出:102
解释:一种最优解决方案如下:
- 选择开头处的整数 -5 ,[-5,-3,-3,-2,7,1] ,得 -5 * -10 = 50 分,累加到分数中。
- 选择开头处的整数 -3 ,[-3,-3,-2,7,1] ,得 -3 * -5 = 15 分,累加到分数中。
- 选择开头处的整数 -3 ,[-3,-2,7,1] ,得 -3 * 3 = -9 分,累加到分数中。
- 选择末尾处的整数 1 ,[-2,7,1] ,得 1 * 4 = 4 分,累加到分数中。
- 选择末尾处的整数 7 ,[-2,7] ,得 7 * 6 = 42 分,累加到分数中。
总分数为 50 + 15 - 9 + 4 + 42 = 102 。

n == nums.length
m == multipliers.length
1 <= m <= 103
m <= n <= 105
-1000 <= nums[i], multipliers[i] <= 1000

分析

qujain.png

C++ 代码

class Solution {
public:typedef long long LL;int n,m,ans=INT_MIN;int maximumScore(vector<int>& nums, vector<int>& multipliers) {n=nums.size(),m=multipliers.size();vector<vector<int> >dp(m+2,vector<int>(m+2,INT_MIN));dp[0][0]=0;for(int k=1;k<=m;k++)   //枚举一共选取多少个元素{for(int i=0;i<=k;i++)   //i从第0个元素到第k个元素{int j=k-i;if(i) dp[i][j]=max(dp[i][j],dp[i-1][j]+multipliers[k-1]*nums[i-1]);if(j) dp[i][j]=max(dp[i][j],dp[i][j-1]+multipliers[k-1]*nums[n-j]);if(k==m) ans=max(ans,dp[i][j]); //k==m时为所有元素都取到了,此时取最大价值}}return ans;}
};

http://www.ppmy.cn/news/209551.html

相关文章

Problem C(HDU-5687)

Problem Description 度熊手上有一本神奇的字典&#xff0c;你可以在它里面做如下三个操作&#xff1a; 1、insert : 往神奇字典中插入一个单词 2、delete: 在神奇字典中删除所有前缀等于给定字符串的单词 3、search: 查询是否在神奇字典中有一个字符串的前缀等于给定的字符…

5687. 执行乘法运算的最大分数

难度中等 给你两个长度分别 n 和 m 的整数数组 nums 和 multipliers &#xff0c;其中 n > m &#xff0c;数组下标 从 1 开始 计数。 初始时&#xff0c;你的分数为 0 。你需要执行恰好 m 步操作。在第 i 步操作&#xff08;从 1 开始 计数&#xff09;中&#xff0c;需要…

HUD 5687(字典树)

反思&#xff1a;之前在删除单词的时候&#xff0c;只是删除掉单词前缀以后的字符&#xff0c;而没有把整个单词都删除掉&#xff0c;导致WA了很多次。 高手请略过... AC代码&#xff1a; #define _CRT_SECURE_NO_WARNINGS #include<iostream> #include<string.h&g…

(转载)基于鱼群算法的函数寻优算法(matlab实现)

1 理论基础 1.1 人工鱼群算法概述 人工鱼群算法是李晓磊等人于2002年提出的一类基于动物行为的群体智能优化算法。该算法是通过模拟鱼类的觅食、聚群、追尾、随机等行为在搜索域中进行寻优&#xff0c;是集群体智能思想的一个具体应用。生物的视觉是极其复杂的&#xff0c;它…

P5687 [CSP-SJX2019] 网格图(Kruskal扩展)

题目链接 Kruskal 思想的扩展&#xff0c;一开始想到了贪心取各行各列中的最小边权&#xff0c;但是没有把握好环的判断问题&#xff0c;只敲了个裸的 Kruskal 水了水&#xff0c;后面参考了洛谷第一篇的题解&#xff0c;其实就是简单地记录一下已经取的行/列的数目就行啦… #…

HDU5687 Problem C【字典树】

Problem C Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 2772 Accepted Submission(s): 768 Problem Description 度熊手上有一本神奇的字典&#xff0c;你可以在它里面做如下三个操作&#xff1a; …

HDU 5687 Problem C 字典树

Problem C Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 2902 Accepted Submission(s): 793 Problem Description 度熊手上有一本神奇的字典&#xff0c;你可以在它里面做如下三个操作&#xff1a; …

HDU 5687 Problem C

Problem Description 度熊手上有一本神奇的字典&#xff0c;你可以在它里面做如下三个操作&#xff1a; 1、insert : 往神奇字典中插入一个单词 2、delete: 在神奇字典中删除所有前缀等于给定字符串的单词 3、search: 查询是否在神奇字典中有一个字符串的前缀等于给定的字符串 …