力扣11.1

2518. 好分区的数目

给你一个正整数数组 nums 和一个整数 k 。

分区 的定义是：将数组划分成两个有序的 组 ，并满足每个元素 恰好 存在于 某一个 组中。如果分区中每个组的元素和都大于等于 k ，则认为分区是一个好分区。

返回 不同 的好分区的数目。由于答案可能很大，请返回对 109 + 7 取余 后的结果。

如果在两个分区中，存在某个元素 nums[i] 被分在不同的组中，则认为这两个分区不同。

数据范围

• 1 <= nums.length, k <= 1000
• 1 <= nums[i] <= 109

分析

逆向思维，由于元素和大于等于$k$的个数不是很好算，因此我们计算元素和小于$k$的个数，由于每个数都必须被选择，因此实际我们考虑第一个集合的方案个数即可，这样就可以转化为01背包问题，我们令$dp[i][j]$为前$i$个数，总和为$j$的个数，对于第$i$个数，有两种决策

• 选第$i$个数：$dp[i][j]=dp[i-1][j]+dp[i-1][j-nums[i]]$
• 不选第$i$个数：$dp[i][j]=dp[i-1][j]$

对于不选第$i$个数，实际就是将他放到第二个集合
最后不合法的方案个数为$err={\sum }_{i=0}^{k-1}dp[n][i]$（其中n为nums的个数），因为集合一和二若互换元素也算一种方案，最后不合法方案$err\ast 2$
**注意：**若${\sum }_{i=0}^{n-1}nums[i]<2\ast k$，此时需要进行特判，因为在计算不合法数组方案的时候最后$err\ast 2$会重复计算
考虑这样的例子，$k=10,nums[]=1,2,3,4$
此时若第一个集合方案有{1}{2}{3}{4}{1,2}{1,3}{1,4}{2,3}{2,4}{3,4}{1,2,3}{1,2,4}{1,3,4}{2,3,4}{1,2,3,4}，对于集合1为{1}的情况，集合2为{2,3,4}，但是{2,3,4}也在集合1的方案中，因此实际此时已经包含了集合1：{1}集合2：{2,3,4}，和集合1：{2,3,4}，集合2：{1}的情况，但是最后err仍然乘了2，所以多算了一倍

代码

typedef long long LL;
class Solution {
public:const static LL N = 1005, mod = 1e9 + 7;LL dp[N][N];LL qpow(LL a, LL n) {LL res = 1;while(n) {if(n & 1) res = res * a % mod;a = a % mod * a % mod;n >>= 1;}return res;}int countPartitions(vector<int>& nums, int k) {int n = nums.size();LL tres = 0;for(auto tk : nums) {tres += tk;}if(tres < 2 * k) return 0;dp[0][0] = 1;for(int i = 0; i < n; i ++ ) {for(int j = 0; j < k; j ++ ) {dp[i + 1][j] = dp[i][j];if(j >= nums[i]) dp[i + 1][j] += dp[i][j - nums[i]];dp[i + 1][j] %= mod;}}LL t = 0;for(int i = 0; i < k; i ++ ) {t += dp[n][i];t %= mod;}t *= 2;LL res = ((qpow(2, n) - t + mod) % mod + mod) % mod; return res;}
};

---

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

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

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

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

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

数据范围

• n == energyDrinkA.length == energyDrinkB.length
• 3 <= n <= 105
• 1 <= energyDrinkA[i], energyDrinkB[i] <= 105

分析

类似于打家劫舍，令dp[i][0]表示第i个数选择A数组的最大能量和，dp[i][1]表示第i个数选择B数组的最大能量和，状态转移如下：

• $dp[i][0]=max(dp[i-2][1],dp[i-1][0])+A[i]$
• $dp[i][1]=max(dp[i-2][0],dp[i-1][1])+B[i]$

考虑先选A和先选B两种情况

代码

typedef long long LL;
class Solution {
public:const static int N = 1e5 + 5;LL dp[N][2];LL maxEnergyBoost(vector<int>& energyDrinkA, vector<int>& energyDrinkB) {int n = energyDrinkA.size();dp[1][0] = energyDrinkA[0];for(int i = 1; i < n; i ++ ) {dp[i + 1][1] = max(dp[i - 1][0], dp[i][1]) + energyDrinkB[i];dp[i + 1][0] = max(dp[i][0], dp[i - 1][1]) + energyDrinkA[i];}LL res = max(dp[n][0], dp[n][1]);cout << dp[n][0] << " " << dp[n][1] << endl;memset(dp, 0, sizeof(dp));dp[1][1] = energyDrinkB[0];for(int i = 1; i < n; i ++ ) {dp[i + 1][0] = max(dp[i - 1][1], dp[i][0]) + energyDrinkA[i];dp[i + 1][1] = max(dp[i][1], dp[i - 1][0]) + energyDrinkB[i];}res = max(res, dp[n][0]);res = max(res, dp[n][1]);return res;}
};