Leetcode 3259. 超级饮料的最大强化能量

动态规划。

f[i][0/1]表示前i个且最后选A或B的方案的集合。

所以f[i][0]=max(f[i-1][0],f[i-2][1])+A[i]。f[i][1]同理。

 1 typedef long long LL;
 2 const int N = 1e5+10;
 3 LL f[N][2];
 4 class Solution {
 5 public:
 6     LL maxEnergyBoost(vector<int>& A, vector<int>& B) {
 7         memset(f,0,sizeof f);
 8         int n=A.size();
 9         for(int i=0;i<A.size();i++){
10             int j=i+1;
11             f[j][0]=f[j-1][0]+A[i];
12             if(j>=2)
13                 f[j][0]=max(f[j][0],f[j-2][1]+A[i]);
14 
15             f[j][1]=f[j-1][1]+B[i];
16             if(j>=2)
17                 f[j][1]=max(f[j][1],f[j-2][0]+B[i]);
18             
19         }
20         return max(f[n][0],f[n][1]);
21     }
22 };