leetcode 第 48 场双周赛
LeetCode 48
2023-09-27 14:27:45 时间
第三题:1798. 你能构造出连续值的最大数目
思路:就是找到最小的不能被表示的整数
贪心,如果$[0, sum_{i}]$ 都能被表示出来,若$a_{i+1} > sum_{i}$,则$sum_i + 1$就不能被表示;若$a_{i+1} <= Sum_{i}$,则 $[0, Sum_{i+1}]$ 都能被表示;
所以,遍历,判断每一个 $a_i$ 即可。
class Solution { public: int getMaximumConsecutive(vector<int>& coins) { sort(coins.begin(), coins.end()); int sum = 0; for(auto x : coins) { if(x > sum+1) return sum+1; sum += x; } return sum+1; } };
第四题:1799. N 次操作后的最大分数和
思路:基本的状压DP,$dp[i] = max(dp[i], dp[i - (1<<j) - (1<<k)] + score)$
class Solution { public: int gcd(int a, int b) { return b==0 ? a : gcd(b, a%b); } int maxScore(vector<int>& nums) { int n = nums.size(); vector<int>dp(1<<n, 0); for(int i = 0;i < (1 << n);i++) { int cnt = 0; for(int j = 0;j < n;j++) if(i & (1<<j)) cnt++; if(cnt%2) continue; for(int j = 0;j < n;j++) for(int k = j+1;k < n;k++) if(((i>>j)&1) == 1 && ((i>>k)&1) == 1) { // cout << i << " " << i-(1<<j)-(1<<k) << endl; dp[i] = max(dp[i], dp[i-(1<<j)-(1<<k)] + gcd(nums[j], nums[k]) * ((n-cnt)/2+1)); } } return dp[(1<<n)-1]; } };
相关文章
- LeetCode_栈_中等_1003.检查替换后的词是否有效
- LeetCode_贪心算法_简单_409.最长回文串
- LeetCode_单调栈_中等_316.去除重复字母
- LeetCode_二叉搜索树_简单_108.将有序数组转换为二叉搜索树
- LeetCode_动态规划_中等_198.打家劫舍
- LeetCode·117.填充每个节点的下一个右侧节点指针||·层次遍历
- Leetcode_num13_Climbing Stairs
- 【算法】动态规划 ⑦ ( LeetCode 55. 跳跃游戏 | 算法分析 | 代码示例 )
- [LeetCode] 673. Number of Longest Increasing Subsequence 最长递增序列的个数
- [LeetCode] 37. Sudoku Solver 求解数独
- [LeetCode] 219. Contains Duplicate II 包含重复元素 II
- leetcode 48 旋转图像
- leetcode 139 单词拆分
- leetcode 376摆动序列