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

news/2024/10/30 9:21:45/

给你两个长度分别 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

采用动态规划的方法是最直接的一种处理方法:
这是一种求最值的动态规划类题型:处理该问题的思路:
1,确定状态:(1),确定最后一步;(2),转化为子问题
2,列出状态转移方程
3,初始化条件和边界情况
4,确定计算顺序

class Solution
{
public:int maximumScore(vector<int>& nums, vector<int>& multipliers) {int n = multipliers.size();vector<vector<int>> dp(n + 1, vector<int>(n + 1, -1e9));dp[0][0] = 0;for (int left = 0; left < n; left++) {for (int right = 0; left + right < n; right++) {dp[left + 1][right] = max(dp[left + 1][right], dp[left][right] + multipliers[left + right] * nums[left]);dp[left][right + 1] = max(dp[left][right + 1], dp[left][right] + multipliers[left + right] * nums[nums.size() - 1 - right]);}}int ret = -1e9;for (int i = 0; i <= n; ++i) {ret = max(ret, dp[i][n - i]);}return ret;}
};

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

相关文章

【题解】LuoGu5687:[CSP-SJX2019]网格图

原题传送门 肯定是让你一排一排的考虑 那就一排一排的考虑 暴力做法就是暴力 k r u s k a l kruskal kruskal&#xff0c;那么怎么把一整排看成一条边&#xff1f;这样就可以满分了 根据 k r u s k a l kruskal kruskal我们可以知道&#xff0c;只要每次选取最小的边且还未联通…

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

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

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; …