网站建设个人网银,新产品推广,找人做网站要准备什么软件,珠海汽车网站建设本文涉及知识点
动态规划 区间dp 位运算
LeetCode100259. 划分数组得到最小的值之和
给你两个数组 nums 和 andValues#xff0c;长度分别为 n 和 m。 数组的 值 等于该数组的 最后一个 元素。 你需要将 nums 划分为 m 个 不相交的连续 子数组#xff0c;对于第 ith 个子数…本文涉及知识点
动态规划 区间dp 位运算
LeetCode100259. 划分数组得到最小的值之和
给你两个数组 nums 和 andValues长度分别为 n 和 m。 数组的 值 等于该数组的 最后一个 元素。 你需要将 nums 划分为 m 个 不相交的连续 子数组对于第 ith 个子数组 [li, ri]子数组元素的按位AND运算结果等于 andValues[i]换句话说对所有的 1 i mnums[li] nums[li 1] … nums[ri] andValues[i] 其中 表示按位AND运算符。 返回将 nums 划分为 m 个子数组所能得到的可能的 最小 子数组 值 之和。如果无法完成这样的划分则返回 -1 。 示例 1 输入 nums [1,4,3,3,2], andValues [0,3,3,2] 输出 12 解释 唯一可能的划分方法为 [1,4] 因为 1 4 0 [3] 因为单元素子数组的按位 AND 结果就是该元素本身 [3] 因为单元素子数组的按位 AND 结果就是该元素本身 [2] 因为单元素子数组的按位 AND 结果就是该元素本身 这些子数组的值之和为 4 3 3 2 12 示例 2
输入 nums [2,3,5,7,7,7,5], andValues [0,7,5]
输出 17
解释
划分 nums 的三种方式为
[[2,3,5],[7,7,7],[5]] 其中子数组的值之和为 5 7 5 17 [[2,3,5,7],[7,7],[5]] 其中子数组的值之和为 7 7 5 19 [[2,3,5,7,7],[7],[5]] 其中子数组的值之和为 7 7 5 19 子数组值之和的最小可能值为 17
示例 3
输入 nums [1,2,3,4], andValues [2]
输出 -1
解释
整个数组 nums 的按位 AND 结果为 0。由于无法将 nums 划分为单个子数组使得元素的按位 AND 结果为 2因此返回 -1。 提示 1 n nums.length 104 1 m andValues.length min(n, 10) 1 nums[i] 105 0 andValues[j] 105
动态规划的位运算
f(i,j) x : i j \Large\And_{x:i}^j x:ij vNext[cur] 记录符合以下条件之一的next 一next-1 cur。 二f(i,next) ≠ \neq f(i,next-1)。 iBitCnt log(max(nums[i]) ≈ \approx ≈ 22 显然next的数量不会超过iBitCnt。 如果f(i,j)发生变化至少一个二进制1变成0。
动态规划
动态规划的状态表示
dp[len][cur] 表示将nums[0…cur]划分为len个区间的最小和。 空间复杂度O(nm)
动态规划的转移方程
r个区间向r1个区间转移时 如果f(cur,next) 等于 andValues[r-1]则: MinSelf(dp[r1][x],dp[r][cur-1]nums[x]) x ∈ [ n e x t , n e x t 的下一个值 ) 这样值设置的时间复杂度是 \in[next,next的下一个值) 这样值设置的时间复杂度是 ∈[next,next的下一个值)这样值设置的时间复杂度是 O ( m × n × i B i t C n t × n ) O(m \times n \times iBitCnt \times n ) O(m×n×iBitCnt×n) 超时了。 只更新x next其它的用二种方式更新 如果 (nums[cur] andValues[r-1]) andValues[r-1] 则MinSelf(dp[r][cur],dp[r][cur-1]) 时间复杂度$ O ( m × n × i B i t C n t ) O(m \times n \times iBitCnt ) O(m×n×iBitCnt)
动态规划的初始值
枚举第一个区间
动态规范的返回值
dp.back().back()
动态规划的填表顺序
len 从1到m_r-1。 cur从1到m_c-1
代码
核心代码
templateclass ELE,class ELE2
void MinSelf(ELE* seft, const ELE2 other)
{*seft min(*seft,(ELE) other);
}templateclass ELE
void MaxSelf(ELE* seft, const ELE other)
{*seft max(*seft, other);
}class Solution {
public:int minimumValueSum(vectorint nums, vectorint andValues) {const int iBitCnt 22;m_r andValues.size();m_c nums.size();const int iMax (1 iBitCnt) - 1;vectorvectorint dp(m_r1,vectorint(m_c, m_iNotMay));int iAnd iMax;for (int i 0; i m_c; i) {iAnd nums[i];if (iAnd andValues[0]) {dp[1][i] nums[i];}}vectorsetint vNext(m_c);{vectorint next(iBitCnt, m_c);for (int i nums.size() - 1; i 0; i--) {vNext[i] setint(next.begin(), next.end());vNext[i].emplace(i);vNext[i].erase(m_c);for (int bit 0; bit iBitCnt; bit){bool b (1 bit) nums[i];if (!b) {next[bit] i;}}}}for (int r 1; r m_r; r){for (int cur 1; cur m_c; cur){int iAdd iMax;for (const auto next : vNext[cur]) {iAdd nums[next];if (andValues[r] iAdd) {MinSelf(dp[r 1][next], dp[r][cur - 1] nums[next]);}}if ((andValues[r - 1] nums[cur]) andValues[r - 1]) {MinSelf(dp[r][cur], dp[r][cur - 1]nums[cur]-nums[cur-1]);} } }{int r m_r;for (int cur 1; cur m_c; cur){ if ((andValues[r - 1] nums[cur]) andValues[r - 1]) {MinSelf(dp[r][cur], dp[r][cur - 1] nums[cur] - nums[cur - 1]);}}}const int iRet dp.back().back();return (iRet 1000000) ? -1 : iRet;}int m_r,m_c;const int m_iNotMay 1000000000;
};测试用例
templateclass T
void Assert(const T t1, const T t2)
{assert(t1 t2);
}templateclass T
void Assert(const vectorT v1, const vectorT v2)
{if (v1.size() ! v2.size()){assert(false);return;}for (int i 0; i v1.size(); i){Assert(v1[i], v2[i]);}}int main()
{vectorint nums, andValues;int k;{Solution sln;nums { 1, 9, 8, 8 }, andValues { 1,8 };auto res sln.minimumValueSum(nums, andValues);Assert(9, res);}{Solution sln;nums { 1, 3, 2, 4, 7, 5, 3 }, andValues { 0, 5, 3 };auto res sln.minimumValueSum(nums, andValues);Assert(12, res);}{Solution sln;nums { 1, 4, 3, 3, 2 }, andValues { 0, 3, 3, 2 };auto res sln.minimumValueSum(nums, andValues);Assert(12, res);}//vectorint nums { 3,6,9 };//int k;////{// Solution sln;// nums { 3,6,9 }, k 3;// auto res sln.findKthSmallest(nums, k);// Assert(9LL, res);//}}扩展阅读
视频课程
有效学习明确的目标 及时的反馈 拉伸区难度合适可以先学简单的课程请移步CSDN学院听白银讲师也就是鄙人的讲解。 https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了为老板分忧请学习C#入职培训、C入职培训等课程 https://edu.csdn.net/lecturer/6176
相关下载
想高屋建瓴的学习算法请下载《喜缺全书算法册》doc版 https://download.csdn.net/download/he_zhidan/88348653
我想对大家说的话闻缺陷则喜是一个美好的愿望早发现问题早修改问题给老板节约钱。子墨子言之事无终始无务多业。也就是我们常说的专业的人做专业的事。如果程序是一条龙那算法就是他的是睛
测试环境
操作系统win7 开发环境 VS2019 C17 或者 操作系统win10 开发环境 VS2022 C17 如无特殊说明本算法用**C**实现。
