【LeetCode周赛】3117. 划分数组得到最小的值之和 | 动态规划 | 困难

2024-04-16 23:04

本文主要是介绍【LeetCode周赛】3117. 划分数组得到最小的值之和 | 动态规划 | 困难,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目内容

原题链接

给你两个数组 numsandValues,长度分别为 nm

数组的 等于该数组的 最后一个 元素。

你需要将 nums 划分为 m 个 不相交的连续 子数组,对于第 ith 个子数组 [li, ri],子数组元素的按位AND运算结果等于 andValues[i],换句话说,对所有的 1 <= i <= m,nums[li] & nums[li + 1] & ... & nums[ri] == andValues[i] ,其中 & 表示按位AND运算符。

返回将 nums 划分为 m 个子数组所能得到的可能的 最小 子数组 之和。如果无法完成这样的划分,则返回 -1

数据范围

  • 1 <= n == nums.length <= 10000
  • 1 <= m == andValues.length <= min(n, 10)
  • 1 <= nums[i] < 100000
  • 0 <= andValues[j] < 100000

题解

为了方便描述,所有下标都从 1 1 1 开始。

暴力解法

状态定义

考虑 d p [ j ] [ i ] dp[j][i] dp[j][i] 表示考虑前 i i i 个元素,前 j j j 组,第 j j j 组的最后一个元素是 n u m s [ i ] nums[i] nums[i] 的最小子数组值之和。

状态转移

d p [ j ] [ i ] = min ⁡ k = j − 1 i − 1 ( d p [ j − 1 ] [ k ] + n u m s [ i ] ) dp[j][i]=\min\limits_{k=j-1}^{i-1} (dp[j-1][k]+nums[i]) dp[j][i]=k=j1mini1(dp[j1][k]+nums[i])

时间复杂度: O ( 17 n 2 m ) O(17n^2m) O(17n2m)

优化解法1

可以发现的是,从 i i i 往前一直进行与运算,整体是一个单调不增的,所以显然可以二分。

二分出最小的 l l l ,满足 nums[l]&nums[l+1]&...&nums[i]=andValues[j]
二分出最大的 r r r,满足 nums[r]&nums[r+1]&...&nums[i]=andValues[j]

然后 d p [ j ] [ i ] = min ⁡ k = l r ( d p [ j − 1 ] [ k ] + n u m s [ i ] ) dp[j][i]=\min\limits_{k=l}^{r} (dp[j-1][k]+nums[i]) dp[j][i]=k=lminr(dp[j1][k]+nums[i])

这部分的 min ⁡ k = l r ( d p [ j − 1 ] [ k ] ) \min\limits_{k=l}^{r} (dp[j-1][k]) k=lminr(dp[j1][k]) 是可以用一个 RMQ 来维护的。

时间复杂度: O ( 17 n m log ⁡ n ) O(17nm\log n) O(17nmlogn)

优化解法 2

上述因为满足单调性,所以考虑双指针。

整体维护一个 l l l r r r,可以发现的是,当 i i i 递增时, l l l r r r 也是单调不减的,所以类似双指针的做法维护 l l l r r r ,使得满足上述情况即可。

时间复杂度: O ( 17 n m ) O(17nm) O(17nm)

代码

class Solution {
public:int minimumValueSum(vector<int>& nums, vector<int>& andValues) {const int MAXBIT = 17;const int INF = 0x3f3f3f3f;int n = nums.size();int m = andValues.size();nums.insert(nums.begin(), 0);andValues.insert(andValues.begin(), 0);// dp[j][i] 表示前 j 组和前 i 个元素,第 j 组的最后一个元素是 nums[i] 的情况下的最小权值和// dp[j][i] = min(dp[j - 1][k]) + nums[i]// 考虑 i ,满足 [k + 1, i]vector<vector<int>> pre(MAXBIT, vector<int>(n + 1));for (int j = 0; j < MAXBIT; ++j)for (int i = 1; i <= n; ++i)pre[j][i] = pre[j][i - 1] + (nums[i] >> j & 1);vector<vector<int>> dp(m + 1, vector<int>(n + 1, INF));dp[0][0] = 0;vector<vector<int>> rmq(MAXBIT, vector<int>(n + 1, INF));vector<int> lg(n + 1);for (int i = 2; i <= n; ++i) lg[i] = lg[i >> 1] + 1;auto update = [&](vector<int>& val) {for (int i = 0; i <= n; ++i) rmq[0][i] = val[i];for (int j = 1; j < MAXBIT; ++j)for (int i = 0; i + (1 << j) - 1 <= n; ++i)rmq[j][i] = min(rmq[j - 1][i], rmq[j - 1][i + (1 << (j - 1))]);};auto query = [&](int l, int r) {if (l > r) return INF;int len = r - l + 1;int b = lg[len];return min(rmq[b][l], rmq[b][r - (1 << b) + 1]);};update(dp[0]);auto check = [&](int l, int r, int andV) -> int {int res = 0;for (int j = 0; j < MAXBIT; ++j)if (pre[j][r] - pre[j][l - 1] == r - l + 1)res |= 1 << j;// 0 表示整过了if ((res & andV) != andV) return 0;// 1 表示 res == andVif (res == andV) return 1;// 2 表示 andV 是 res 的子集return 2;};for (int j = 1; j <= m; ++j) {int andV = andValues[j];int l = j, r = j;for (int i = j; i <= n; ++i) {/*优化点在于:我们看暴力的部分:从后往前枚举,什么时候 break ?当 (mask & andV) != andV ,就可以 break 了这部分可以二分,为什么可以二分?因为我们从 i 往前枚举 pi ,这个 mask 在每个二进制位以及整体都是单调下降的二分出 res == andV 的最小的 l继续二分出 res == andV 的最大的 r*/// 暴力解法做法// int mask = -1;// for (int pi = i; pi >= 1; --pi) {//     mask &= nums[pi];//     if (mask == andV) dp[j][i] = min(dp[j][i], dp[j - 1][pi - 1] + nums[i]);//     if ((mask & andV) != andV) break;// }// 优化解法1,二分做法//int left = j, right = i;//while (left < right) {//    int mid = (left + right) >> 1;//    if (check(mid, i, andV) == 0) left = mid + 1;//    else right = mid;//}////int flag = check(left, i, andV);//if (flag != 1) continue;//int l = left;////right = i;//while (left < right) {//    int mid = (left + right + 1) >> 1;//    if (check(mid, i, andV) == 1) left = mid;//    else right = mid - 1;//}//int r = left;// 优化解法2双指针做法// 首先 l 应该是 == 0 的全部崩掉while (l < i && check(l, i, andV) == 0) l += 1;if (check(l, i, andV) != 1) continue;r = l;while (r < i && check(r, i, andV) == 1) r += 1;if (check(r, i, andV) == 2) r -= 1;dp[j][i] = min(dp[j][i], query(l - 1, r - 1) + nums[i]);}update(dp[j]);}return dp[m][n] >= INF ? -1 : dp[m][n];}
};

这篇关于【LeetCode周赛】3117. 划分数组得到最小的值之和 | 动态规划 | 困难的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/910144

相关文章

C++原地删除有序数组重复项的N种方法

《C++原地删除有序数组重复项的N种方法》给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度,不要使用额外的数组空间,你必须在原地修改输入数组并在使用O(... 目录一、问题二、问题分析三、算法实现四、问题变体:最多保留两次五、分析和代码实现5.1、问题分析5.

mybatis-plus 实现查询表名动态修改的示例代码

《mybatis-plus实现查询表名动态修改的示例代码》通过MyBatis-Plus实现表名的动态替换,根据配置或入参选择不同的表,本文主要介绍了mybatis-plus实现查询表名动态修改的示... 目录实现数据库初始化依赖包配置读取类设置 myBATis-plus 插件测试通过 mybatis-plu

Java中数组转换为列表的两种实现方式(超简单)

《Java中数组转换为列表的两种实现方式(超简单)》本文介绍了在Java中将数组转换为列表的两种常见方法使用Arrays.asList和Java8的StreamAPI,Arrays.asList方法简... 目录1. 使用Java Collections框架(Arrays.asList)1.1 示例代码1.

基于Canvas的Html5多时区动态时钟实战代码

《基于Canvas的Html5多时区动态时钟实战代码》:本文主要介绍了如何使用Canvas在HTML5上实现一个多时区动态时钟的web展示,通过Canvas的API,可以绘制出6个不同城市的时钟,并且这些时钟可以动态转动,每个时钟上都会标注出对应的24小时制时间,详细内容请阅读本文,希望能对你有所帮助...

Vue中动态权限到按钮的完整实现方案详解

《Vue中动态权限到按钮的完整实现方案详解》这篇文章主要为大家详细介绍了Vue如何在现有方案的基础上加入对路由的增、删、改、查权限控制,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、数据库设计扩展1.1 修改路由表(routes)1.2 修改角色与路由权限表(role_routes)二、后端接口设计

前端 CSS 动态设置样式::class、:style 等技巧(推荐)

《前端CSS动态设置样式::class、:style等技巧(推荐)》:本文主要介绍了Vue.js中动态绑定类名和内联样式的两种方法:对象语法和数组语法,通过对象语法,可以根据条件动态切换类名或样式;通过数组语法,可以同时绑定多个类名或样式,此外,还可以结合计算属性来生成复杂的类名或样式对象,详细内容请阅读本文,希望能对你有所帮助...

Nginx实现动态封禁IP的步骤指南

《Nginx实现动态封禁IP的步骤指南》在日常的生产环境中,网站可能会遭遇恶意请求、DDoS攻击或其他有害的访问行为,为了应对这些情况,动态封禁IP是一项十分重要的安全策略,本篇博客将介绍如何通过NG... 目录1、简述2、实现方式3、使用 fail2ban 动态封禁3.1 安装 fail2ban3.2 配

Vue3中的动态组件详解

《Vue3中的动态组件详解》本文介绍了Vue3中的动态组件,通过`component:is=动态组件名或组件对象/component`来实现根据条件动态渲染不同的组件,此外,还提到了使用`markRa... 目录vue3动态组件动态组件的基本使用第一种写法第二种写法性能优化解决方法总结Vue3动态组件动态

C++一个数组赋值给另一个数组方式

《C++一个数组赋值给另一个数组方式》文章介绍了三种在C++中将一个数组赋值给另一个数组的方法:使用循环逐个元素赋值、使用标准库函数std::copy或std::memcpy以及使用标准库容器,每种方... 目录C++一个数组赋值给另一个数组循环遍历赋值使用标准库中的函数 std::copy 或 std::

Android 悬浮窗开发示例((动态权限请求 | 前台服务和通知 | 悬浮窗创建 )

《Android悬浮窗开发示例((动态权限请求|前台服务和通知|悬浮窗创建)》本文介绍了Android悬浮窗的实现效果,包括动态权限请求、前台服务和通知的使用,悬浮窗权限需要动态申请并引导... 目录一、悬浮窗 动态权限请求1、动态请求权限2、悬浮窗权限说明3、检查动态权限4、申请动态权限5、权限设置完毕后