提高网站公信力 单仁,台州建站服务,怎么自己免费创建网站,网站没有被收录2518. 好分区的数目
给你一个正整数数组 nums 和一个整数 k 。
分区 的定义是#xff1a;将数组划分成两个有序的 组 #xff0c;并满足每个元素 恰好 存在于 某一个 组中。如果分区中每个组的元素和都大于等于 k #xff0c;则认为分区是一个好分区。
返回 不同 的好分区…2518. 好分区的数目
给你一个正整数数组 nums 和一个整数 k 。
分区 的定义是将数组划分成两个有序的 组 并满足每个元素 恰好 存在于 某一个 组中。如果分区中每个组的元素和都大于等于 k 则认为分区是一个好分区。
返回 不同 的好分区的数目。由于答案可能很大请返回对 109 7 取余 后的结果。
如果在两个分区中存在某个元素 nums[i] 被分在不同的组中则认为这两个分区不同。
数据范围
1 nums.length, k 10001 nums[i] 109
分析
逆向思维由于元素和大于等于 k k k的个数不是很好算因此我们计算元素和小于 k k k的个数由于每个数都必须被选择因此实际我们考虑第一个集合的方案个数即可这样就可以转化为01背包问题我们令 d p [ i ] [ j ] dp[i][j] dp[i][j]为前 i i i个数总和为 j j j的个数对于第 i i i个数有两种决策
选第 i i i个数 d p [ i ] [ j ] d p [ i − 1 ] [ j ] d p [ i − 1 ] [ j − n u m s [ i ] ] dp[i][j]dp[i-1][j]dp[i-1][j-nums[i]] dp[i][j]dp[i−1][j]dp[i−1][j−nums[i]]不选第 i i i个数 d p [ i ] [ j ] d p [ i − 1 ] [ j ] dp[i][j]dp[i-1][j] dp[i][j]dp[i−1][j]
对于不选第 i i i个数实际就是将他放到第二个集合 最后不合法的方案个数为 e r r ∑ i 0 k − 1 d p [ n ] [ i ] err\sum_{i0}^{k-1}dp[n][i] err∑i0k−1dp[n][i]其中n为nums的个数因为集合一和二若互换元素也算一种方案最后不合法方案 e r r ∗ 2 err*2 err∗2 **注意**若 ∑ i 0 n − 1 n u m s [ i ] 2 ∗ k \sum_{i0}^{n-1}nums[i]2*k ∑i0n−1nums[i]2∗k此时需要进行特判因为在计算不合法数组方案的时候最后 e r r ∗ 2 err*2 err∗2会重复计算 考虑这样的例子 k 10 , n u m s [ ] 1 , 2 , 3 , 4 k10,nums[]{1,2,3,4} k10,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(vectorint 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.length3 n 1051 energyDrinkA[i], energyDrinkB[i] 105
分析
类似于打家劫舍令dp[i][0]表示第i个数选择A数组的最大能量和dp[i][1]表示第i个数选择B数组的最大能量和状态转移如下 d p [ i ] [ 0 ] m a x ( d p [ i − 2 ] [ 1 ] , d p [ i − 1 ] [ 0 ] ) A [ i ] dp[i][0]max(dp[i-2][1],dp[i-1][0])A[i] dp[i][0]max(dp[i−2][1],dp[i−1][0])A[i] d p [ i ] [ 1 ] m a x ( d p [ i − 2 ] [ 0 ] , d p [ i − 1 ] [ 1 ] ) B [ i ] dp[i][1]max(dp[i-2][0],dp[i-1][1])B[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(vectorint energyDrinkA, vectorint 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;}
};
