首页 > 其他分享 >2024-11-1-leetcode每日一题-3259. 超级饮料的最大强化能量

2024-11-1-leetcode每日一题-3259. 超级饮料的最大强化能量

时间:2024-11-01 19:19:11浏览次数:7  
标签:11 3259 max 2024 饮料 energyDrinkB 能量 energyDrinkA dp

题目描述

来自未来的体育科学家给你两个整数数组 energyDrinkA 和 energyDrinkB,数组长度都等于 n。这两个数组分别代表 A、B 两种不同能量饮料每小时所能提供的强化能量。

你需要每小时饮用一种能量饮料来 最大化 你的总强化能量。然而,如果从一种能量饮料切换到另一种,你需要等待一小时来梳理身体的能量体系(在那个小时里你将不会获得任何强化能量)。

返回在接下来的 n 小时内你能获得的 最大 总强化能量。

注意 你可以选择从饮用任意一种能量饮料开始。

示例 1:

输入:energyDrinkA = [1,3,1], energyDrinkB = [3,1,1]

输出:5

解释:

要想获得 5 点强化能量,需要选择只饮用能量饮料 A(或者只饮用 B)。

示例 2:

输入:energyDrinkA = [4,1,1], energyDrinkB = [1,1,3]

输出:7

解释:

  • 第一个小时饮用能量饮料 A。
  • 切换到能量饮料 B ,在第二个小时无法获得强化能量。
  • 第三个小时饮用能量饮料 B ,并获得强化能量。

解题思路

首先定义dp[i][j],j为0或1对应饮料A和B,含义为第i次选择饮料j能获得的最大能量。因为切换饮料是需要cd一回合的,所以当前选择了饮料A那么他的前一步可能来自第i - 1步选择A饮料,或者是i - 2步选择B饮料,当前选择了饮料B那么他的前一步可能来自第i - 1步选择B饮料,或者是i - 2步选择A饮料。由此易得状态转移方程为

            dp[i][0] = energyDrinkA[i] + max(dp[i - 1][0], dp[i - 2][1]);

            dp[i][1] = energyDrinkB[i] + max(dp[i - 1][1], dp[i - 2][0]);

最后答案为max(dp[n - 1][0], dp[n - 1][1])

AC代码

class Solution {
public:
    long long maxEnergyBoost(vector<int>& energyDrinkA, vector<int>& energyDrinkB) {
        int n = energyDrinkA.size();
        long long dp[n + 1][2];
        dp[0][0] = energyDrinkA[0]; dp[0][1] = energyDrinkB[0];
        dp[1][0] = dp[0][0] + energyDrinkA[1];
        dp[1][1] = dp[0][1] + energyDrinkB[1];

        for(int i = 2; i < n; i ++) {
            dp[i][0] = energyDrinkA[i] + max(dp[i - 1][0], dp[i - 2][1]);
            dp[i][1] = energyDrinkB[i] + max(dp[i - 1][1], dp[i - 2][0]);
        }

        return max(dp[n - 1][0], dp[n - 1][1]);
    }
};

标签:11,3259,max,2024,饮料,energyDrinkB,能量,energyDrinkA,dp
From: https://blog.csdn.net/qq_51019596/article/details/143422544

相关文章

  • X (Twitter)养号指南:2024最新攻略
    X (Twitter)作为活跃用户数以亿计的社交媒体平台,用户数依然在不断增长,其中巨大的流量吸引着个人用户与品牌和卖家。Twitter养号是有必要的,有大量案例表明养好号,可以大幅度降低账号被冻结的几率,并提升账号的稳定性和影响力,同时,通过合理的养号策略,可以提高内容的曝光率和用户互......
  • CSP-S 2024 游寄
    我不曾忘记很好听的草神歌,打算推完经过就推这个。我的破木箱装满枯萎的花放不下光与壤和新鲜的愿望如果能飞翔去高高的地方撒一张梦的网收集爱的回响你也在听吗落单的孩子啊别害怕别害怕黑夜不会太长悬崖上的花让我为你摘下数一瓣落一瓣就少一朵忧伤......
  • Regex Golf通关记录(11)——解谜篇上
    RegexGolf网址:https://alf.nu/RegexGolfRegexGolf通关解答:RegexGolf通关解答-CSDN博客解谜篇,收的是我开始完全看不出规律的题目。通过查阅资料,弄清题目意图的过程,宛如解谜一般。Tic-tac-toe–Don'tforgetthehorizontals.Tic-tac-toe就是我们小时候玩的井字棋。如果......
  • 11.1随笔
    这里是11.1随笔。题目留档:二叉树遍历应用代码:#includeinclude//二叉树节点结构体structTreeNode{charval;TreeNode*left;TreeNode*right;TreeNode(charx):val(x),left(NULL),right(NULL){}};//根据先序遍历字符串构建二叉树TreeNode*buildTree(std::s......
  • 2024.11.1总结
    本文于github博客同步更新。OI相关:A:分为两种情况处理:\(u\)到\(lca\)和\(lca\)到\(v\)。我的做法是先树剖,将每条链单独拿出来拉出来,根据\(a_i\)和\(b_i\)连边,正反各建一棵树,维护一下\(k\)级祖先。然后从\(u\)到\(v\)的时候每次根据从dfs序由小到大还是由......
  • 《上海市计算机学会竞赛平台2024年8月月赛丙组题目T1 统计得分 T2 等差数列的素性 T3
    T1统计得分内存限制: 256 Mb时间限制: 1000 ms题目描述在一场知识竞赛中,选手答对一题得 11 分,答错不得分且要倒扣 11 分,但扣分不能让分数小于 00。给定一个由 Y 及 N 构成的字符序列,答对记为 Y,答错记为 N。选手一开始从 00 分开始,请输出选手最后的得分......
  • 『模拟赛』多校A层冲刺NOIP2024模拟赛17
    Rank一般A.网络签不上的签到题。首先考虑枚举路径的做法,如果先枚举再计算的话复杂度会是\(\mathcal{O(\binom{n+m-2}{n-1}(n+m))}\)的,稍微优化一点的过程中可以去掉后面的\((n+m)\)。考虑此时我们要记什么,首先遇到加号其前面的值\(z\)就确定了,若上个符号为乘号那么......
  • 浏览器指纹修改指南2024 - 分析Geolocation API实现(十)
    在geolocation.h文件中,可以找到一个私有成员Member<GeoNotifierSet>one_shots_;Member<GeolocationWatchers>watchers_;//GeoNotifiersthatareinthemiddleofinvocation.////|HandleError(error)|and|MakeSuccessCallbacks|needtoclear|one_sho......
  • NOIP2024 模拟赛 #12
    学长出的模拟赛,风格挺好。赛时8:00T1会了一个\(O(n^2\logn)\)的做法,先写一下,看看能不能过样例。8:20过了小样例,大样例跑得慢但是是对的。8:40发现一个好的做法,可以枚举\(c_i\)最小的那一天选了哪个,再枚举\(k\)天,这样纯枚举复杂度是\(O(k)\)的。但是有些细节不太......
  • 11.01模拟赛
    T1把所有的薯片按热量排序,\(l,r\)表示选取的区间的左右端点,当区间中的种类数等于\(k\)时,这个区间合法,更新答案并\(l\)++,否则\(r\)++,直到\(r=n\),最后的话要看\(l\)能否往上加,开始没有写,所以最后一个大样例一直不过,调了20min左右。T2构造题,感觉很难啊,就想着先找最多数量......