题目描述
来自未来的体育科学家给你两个整数数组 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