【动态规划】【C++算法】2518. 好分区的数目

作者推荐

【动态规划】【前缀和】【C++算法】LCP 57. 打地鼠

本文涉及知识点

动态规划汇总

LeetCode:2518. 好分区的数目

给你一个正整数数组 nums 和一个整数 k 。
分区 的定义是：将数组划分成两个有序的 组 ，并满足每个元素 恰好 存在于 某一个 组中。如果分区中每个组的元素和都大于等于 k ，则认为分区是一个好分区。
返回 不同 的好分区的数目。由于答案可能很大，请返回对 109 + 7 取余 后的结果。
如果在两个分区中，存在某个元素 nums[i] 被分在不同的组中，则认为这两个分区不同。
示例 1：
输入：nums = [1,2,3,4], k = 4
输出：6
解释：好分区的情况是 ([1,2,3], [4]), ([1,3], [2,4]), ([1,4], [2,3]), ([2,3], [1,4]), ([2,4], [1,3]) 和 ([4], [1,2,3]) 。
示例 2：
输入：nums = [3,3,3], k = 4
输出：0
解释：数组中不存在好分区。
示例 3：
输入：nums = [6,6], k = 2
输出：2
解释：可以将 nums[0] 放入第一个分区或第二个分区中。
好分区的情况是 ([6], [6]) 和 ([6], [6]) 。
参数范围：
1 <= nums.length, k <= 1000
1 <= nums[i] <= 109

动态规划

动态规划的状态表示

暴力做法：dp[i][j][m] 记录前i个 数子，第一个分区和为j，第二个分区和为m。这样时间复杂度O(109)超时。

状态优化

j+m 显然等于y= ∑ x : 0 i − 1 \Large\sum_{x:0}^{i-1} ∑x:0i−1​nums[x]
{ 第一个分区和为 p r e , 第二个分区和为 j − p r e p r e < k 第一个分区和大于等于 k ，第二个分区和 p r e − k p r e ∈ [ k , 2 k ] \begin{cases} 第一个分区和为pre,第二个分区和为j-pre & pre<k \\ 第一个分区和大于等于k，第二个分区和pre-k & pre\in[k,2k] \end{cases} {第一个分区和为pre,第二个分区和为j−pre第一个分区和大于等于k，第二个分区和pre−k​pre<kpre∈[k,2k]​
pre[j]表示前i个数的形成的分区数量,dp[j]表示前i+1个数。

动态规划的转移方程

分两种情况：nums[i] 属于分区一，属于分区二。

动态规划的初始值

pre[0]=1，其它等于0。

动态规划的填表顺序

i从0到大，前者状态更新后置状态。

动态规划的返回值

pre.back()。

代码

核心代码

template<int MOD = 1000000007>
class C1097Int
{
public:
	C1097Int(long long llData = 0) :m_iData(llData% MOD)
	{

	}
	C1097Int  operator+(const C1097Int& o)const
	{
		return C1097Int(((long long)m_iData + o.m_iData) % MOD);
	}
	C1097Int& operator+=(const C1097Int& o)
	{
		m_iData = ((long long)m_iData + o.m_iData) % MOD;
		return *this;
	}
	C1097Int& operator-=(const C1097Int& o)
	{
		m_iData = (m_iData + MOD - o.m_iData) % MOD;
		return *this;
	}
	C1097Int  operator-(const C1097Int& o)
	{
		return C1097Int((m_iData + MOD - o.m_iData) % MOD);
	}
	C1097Int  operator*(const C1097Int& o)const
	{
		return((long long)m_iData * o.m_iData) % MOD;
	}
	C1097Int& operator*=(const C1097Int& o)
	{
		m_iData = ((long long)m_iData * o.m_iData) % MOD;
		return *this;
	}
	bool operator<(const C1097Int& o)const
	{
		return m_iData < o.m_iData;
	}
	C1097Int pow(long long n)const
	{
		C1097Int iRet = 1, iCur = *this;
		while (n)
		{
			if (n & 1)
			{
				iRet *= iCur;
			}
			iCur *= iCur;
			n >>= 1;
		}
		return iRet;
	}
	C1097Int PowNegative1()const
	{
		return pow(MOD - 2);
	}
	int ToInt()const
	{
		return m_iData;
	}
private:
	int m_iData = 0;;
};

class Solution {
public:
	int countPartitions(vector<int>& nums, int k) {
		vector<C1097Int<>> vPre(2 * k + 1);
		vPre[0] = 1;
		long long llSum = 0;
		for (const auto& n : nums)
		{			
			vector<C1097Int<>> dp(2 * k + 1);
			for (int pre = 0; pre <= 2 * k; pre++)
			{
				const long long sum1 = (pre < k) ? pre : k;
				const long long sum2 = min((long long)k,((pre < k) ? (llSum - pre) : (pre - k)));
				//分区一
				const long long sum11 = min((long long)k, sum1 + n);
				const long long sum22 = min((long long)k, sum2 + n);
				auto Updata = [&dp,&vPre, &pre,&k] (long long sum1, long long sum2)
				{
					if (sum1 < k)
					{
						dp[sum1] += vPre[pre];
					}
					else
					{
						dp[k+sum2] += vPre[pre];
					}
				};
				Updata(sum11, sum2);
				Updata(sum1, sum22);
			}
			vPre.swap(dp);
			llSum += n;
		}
		return vPre.back().ToInt();
	}
};

测试用例


template<class T>
void Assert(const T& t1, const T& t2)
{
	assert(t1 == t2);
}

template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
	if (v1.size() != v2.size())
	{
		assert(false);
		return;
	}
	for (int i = 0; i < v1.size(); i++)
	{
		Assert(v1[i], v2[i]);
	}

}

int main()
{	
	vector<int> nums;
	int k;
	{
		Solution sln;
		nums = { 1, 2, 3, 4 }, k = 4;
		auto res = sln.countPartitions(nums, k);
		Assert(res,6);
	}

	{
		Solution sln;
		nums = { 3, 3, 3 }, k = 4;
		auto res = sln.countPartitions(nums, k);
		Assert(res, 0);
	}

	{
		Solution sln;
		nums = { 6,6 }, k = 2;
		auto res = sln.countPartitions(nums, k);
		Assert(res, 2);
	}
		
}

2023年2月

class C1097Int
{
public:
C1097Int(int iData = 0) :m_iData(iData)
{

 }
 C1097Int  operator+(const C1097Int& o)const
 {
	 return C1097Int(((long long)m_iData + o.m_iData) % s_iMod);
 }
 C1097Int&  operator+=(const C1097Int& o)
 {
	 m_iData = ((long long)m_iData + o.m_iData) % s_iMod;
	 return *this;
 }
 C1097Int&  operator-=(const C1097Int& o)
 {
	 m_iData = (m_iData + s_iMod  - o.m_iData) % s_iMod;
	 return *this;
 }
 C1097Int  operator*(const C1097Int& o)const
 {
	 return((long long)m_iData *o.m_iData) % s_iMod;
 }
 C1097Int&  operator*=(const C1097Int& o)
 {
	m_iData =((long long)m_iData *o.m_iData) % s_iMod;
	 return *this;
 }
 bool operator<(const C1097Int& o)const
 {
	 return m_iData < o.m_iData;
 }
 C1097Int& pow( int n)const
 {
	 C1097Int iRet = 1, iCur = *this;
	while (n)
	{
		if (n & 1)
		{
			iRet *= iCur;
		}
		iCur *= iCur;
		n >>= 1;
	}
	return iRet;
 }
 C1097Int PowNegative1()
 {
	 return pow(s_iMod - 2);
 }
 int ToInt()const
 {
	 return m_iData;
 }

private:
int m_iData = 0;;
static const int s_iMod = 1000000007;
};

int operator+(int iData, const C1097Int& int1097)
{
int iRet = int1097.operator+(C1097Int(iData)).ToInt();
return iRet;
}

int& operator+=(int& iData, const C1097Int& int1097)
{
iData = int1097.operator+(C1097Int(iData)).ToInt();
return iData;
}

int operator*(int iData, const C1097Int& int1097)
{
int iRet = int1097.operator*(C1097Int(iData)).ToInt();
return iRet;
}

int& operator*=(int& iData, const C1097Int& int1097)
{
iData = int1097.operator*(C1097Int(iData)).ToInt();
return iData;
}

class Solution {
public:
int countPartitions(vector& nums, int K) {
//pre0 记录选取的数组和低于k，pre1 记录选取的数组和超过k，未选取的数组和低于k
vector pre0(K), pre1(K);
pre0[0] = 1;
C1097Int iRet;
long long llSum = 0;
for (const auto& n : nums)
{
llSum += n;
vector dp0 = pre0, dp1 = pre1;
iRet += iRet;//已经符合要求的，选取不选取都符合
//选取
for (int pr = 0; pr < K; pr++)
{
const int iSelSum = pr + n;
const auto& preValue = pre0[pr];
if (0 == preValue.ToInt())
{
continue;
}
if (iSelSum< K)
{
dp0[iSelSum] += preValue;
}
else
{
const long long llNoSelSum = llSum - iSelSum;
if (llNoSelSum >= K)
{
iRet += preValue;
}
else
{
dp1[llNoSelSum] += preValue;
}
}
}
//不选取
for (int pr = 0; pr < K; pr++)
{
const int iNoSelSum = pr + n;
const auto& preValue = pre1[pr];
if (0 == preValue.ToInt())
{
continue;
}
if (iNoSelSum < K)
{
dp1[iNoSelSum] += preValue;
}
else
{
iRet += preValue;
}
}
pre0.swap(dp0);
pre1.swap(dp1);
}
return iRet.ToInt();
}
};

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步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 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/380084.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

AVR 328pb ADC基本介绍和使用

AVR 328pb ADC基本介绍和使用

AVR 328pb ADC基本介绍和使用 &#x1f4cd;结合参考同架构lgt8f328p中文文档&#xff1a;http://www.prodesign.com.cn/wp-content/uploads/2023/03/LGT8FX8P_databook_v1.0.4.pdf &#x1f4d8;328pb ADC特性 • 10-bit Resolution 10位分辨率 • 0.5 LSB Integral Non-lin…
阅读更多...
猫头虎分享已解决Bug || JavaScript语法错误（Syntax Error）：SyntaxError: Unexpected token

猫头虎分享已解决Bug || JavaScript语法错误（Syntax Error）：SyntaxError: Unexpected token

博主猫头虎的技术世界 &#x1f31f; 欢迎来到猫头虎的博客 — 探索技术的无限可能&#xff01; 专栏链接&#xff1a; &#x1f517; 精选专栏&#xff1a; 《面试题大全》 — 面试准备的宝典&#xff01;《IDEA开发秘籍》 — 提升你的IDEA技能&#xff01;《100天精通鸿蒙》 …
阅读更多...
leetcode（哈希表）49.字母异位词分组（C++详细解释）DAY5

leetcode（哈希表）49.字母异位词分组（C++详细解释）DAY5

文章目录 1.题目示例提示 2.解答思路3.实现代码结果 4.总结 1.题目 给你一个字符串数组&#xff0c;请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。 字母异位词 是由重新排列源单词的所有字母得到的一个新单词。 示例 示例 1: 输入: strs [“eat”, “tea”…
阅读更多...
Golang的for循环变量和goroutine的陷阱，1.22版本的更新

Golang的for循环变量和goroutine的陷阱，1.22版本的更新

先来看一段golang 1.22版本之前的for循环的代码 package mainimport "fmt"func main() {done : make(chan bool)values : []string{"chen", "hai", "feng"}for _, v : range values {fmt.Println("start")go func() {fmt.P…
阅读更多...
Elasticsearch（四）

Elasticsearch（四）

是这样的前面的几篇笔记&#xff0c;感觉对我没有形成知识体系&#xff0c;感觉乱糟糟的&#xff0c;只是大概的了解了一些基础知识&#xff0c;仅此而已&#xff0c;而且对于这技术栈的学习也是为了在后面的java开发使用&#xff0c;但是这里的API学的感觉有点乱&#xff01;然…
阅读更多...
JavaScript 入门 完整版

JavaScript 入门 完整版

目录 第一个知识点&#xff1a;引入js文件 内部引用: 外部引用: 第二个知识点&#xff1a;javascript的基本语法 定义变量&#xff1a; 条件控制(if - else if - else) 第三个知识点&#xff1a;javascript里的数据类型、运算符&#xff1a; 数字类型 字符串类型 布尔…
阅读更多...
前端JavaScript篇之对执行上下文的理解

前端JavaScript篇之对执行上下文的理解

目录 对执行上下文的理解创建执行上下文 对执行上下文的理解 当我们在执行JavaScript代码时&#xff0c;JavaScript引擎会创建并维护一个执行上下文栈来管理执行上下文。执行上下文有三种类型&#xff1a;全局执行上下文、函数执行上下文和eval函数执行上下文。 在写代码的时…
阅读更多...
FRP内网穿透需要注意的事情

FRP内网穿透需要注意的事情

安全性 SSH设置好密钥后&#xff0c;一定要关闭密码登陆。现在暴力破解策略往往是先派小鸡端口扫描看看谁可以密码访问&#xff0c;如果可以&#xff0c;然后定点爆破就开始了。不允许root登陆。FRP使用token验证。FRP服务端要输出配置文件&#xff0c;info等级就能显示访问ip…
阅读更多...
mac docker 宿主机和容器间网络打通

mac docker 宿主机和容器间网络打通

动因 是这样&#xff0c;笔者最近满怀欣喜入手Docker&#xff0c;看着各种文章命令都是不断点头称道&#xff1a;“嗯嗯&#xff0c;不错不错”,在接下来终于准备大干一场的时候碰壁了&#xff0c;主要情况是说在Mac中跑了第一把的时候发现碰到&#xff0c;虚拟机和宿主机居然…
阅读更多...
C语言笔试题之两数相加（多次反转链表实现）

C语言笔试题之两数相加（多次反转链表实现）

实例要求&#xff1a; 1、给定两个非空链表&#xff08;l1和l2&#xff09;来代表两个非负整数&#xff1b;2、数字最高位位于链表开始位置&#xff1b;3、它们的每个节点只存储一位数字&#xff1b;4、将这两数相加会返回一个新的链表&#xff1b; 案例展示&#xff1a; 实例…
阅读更多...
Leetcode刷题笔记题解（C++）：面试题 08.07. 无重复字符串的排列组合

Leetcode刷题笔记题解（C++）：面试题 08.07. 无重复字符串的排列组合

思路&#xff1a;因为字符之间互不相同&#xff0c;故使用全排列的方式去解题&#xff1b; 字符串长度为n&#xff0c;将第一个字母分别与后面每一个字母进行交换&#xff0c;生成n种不同的全排列&#xff1b;再用第二个元素与后面每一个元素进行交换&#xff0c;生成n - 1种不…
阅读更多...
K8S之运用亲和性设置Pod的调度约束

K8S之运用亲和性设置Pod的调度约束

亲和性 Node节点亲和性硬亲和实践软亲和性实践 Pod节点亲和性和反亲和性pod亲和性硬亲和实践 pod反亲和性 Pod 的yaml文件里 spec 字段中包含一个 affinity 字段&#xff0c;使用一组亲和性调度规则&#xff0c;指定pod的调度约束。 kubectl explain pods.spec.affinity 配置…
阅读更多...
c语言实现io多路复用(select)，进程，线程并发服务器

c语言实现io多路复用(select)，进程，线程并发服务器

io多路复用&#xff08;select&#xff09;代码 #include<myhead.h> #include <sys/select.h> #define PORT 8888 #define IP "192.168.250.100" int main(int argc, char const *argv[]) { //创建套接字int sfd socket(AF_INET, SOCK_STREAM, 0…
阅读更多...
Leetcode—60. 排列序列【困难】

Leetcode—60. 排列序列【困难】

2024每日刷题&#xff08;113&#xff09; Leetcode—60. 排列序列 算法思想 实现代码 class Solution { public:string getPermutation(int n, int k) {vector<int> nums(n);// f[i] i!vector<int> f(n 1, 1); string ans;iota(nums.begin(), nums.end(), 1…
阅读更多...
Blazor入门100天 : 自做一个支持长按事件的按钮组件

Blazor入门100天 : 自做一个支持长按事件的按钮组件

好长时间没继续写这个系列博客了, 不知道大家还记得我吗? 话不多说,直接开撸. 配套源码 demo https://blazor.app1.es/b19LongPressButton ####1. 新建 net8 blazor 工程 b19LongPressButton 至于用什么模式大家各取所需, 我创建的是ssr单工程, 如果大家不小心建立错了按页…
阅读更多...
软考 系统分析师系列知识点之信息系统战略规划方法（4）

软考 系统分析师系列知识点之信息系统战略规划方法（4）

接前一篇文章&#xff1a;软考 系统分析师系列知识点之信息系统战略规划方法&#xff08;3&#xff09; 所属章节&#xff1a; 第7章. 企业信息化战略与实施 第4节. 信息系统战略规划方法 7.4.2 关键成功因素法 关键成功因素&#xff08;Critical Success Factors&#xff0c…
阅读更多...
Vue3.0（五）：Vue-Router 4.x详解

Vue3.0（五）：Vue-Router 4.x详解

Vue-Router详解 vue-router教程 认识前端路由 路由实际上是网络工程中的一个术语 在架构一个网络的时候&#xff0c;常用到两个很重要的设备—路由器和交换机路由器实际上就是分配ip地址&#xff0c;并且维护着ip地址与电脑mac地址的映射关系通过映射关系&#xff0c;路由器…
阅读更多...
放假--寒假自学版 day1（补2.5）

放假--寒假自学版 day1（补2.5）

fread 函数&#xff1a; 今日练习 C语言面试题5道~ 1. static 有什么用途&#xff1f;&#xff08;请至少说明两种&#xff09; 1) 限制变量的作用域 2) 设置变量的存储域 2. 引用与指针有什么区别&#xff1f; 1) 引用必须被初始化&#xff0c;指针不必。 2) 引用初始…
阅读更多...
数据结构与算法-链表(力扣附链接)

数据结构与算法-链表(力扣附链接)

之前我们对C语言进行了一定的学习&#xff0c;有了一些基础之后&#xff0c;我们就可以学习一些比较基础的数据结构算法题了。这部分的知识对于我们编程的深入学习非常有用&#xff0c;对于一些基本的算法&#xff0c;我们学习之后&#xff0c;就可以参加一些编程比赛了&#x…
阅读更多...
java基础(2) 面向对象编程-java核心类

java基础(2) 面向对象编程-java核心类

面向对象 面向对象对应的就是面向过程&#xff0c; 面向过程就是一步一步去操作&#xff0c;你需要知道每一步的步骤。 面向对象的编程以对象为核心&#xff0c;通过定义类描述实体及其行为&#xff0c;并且支持继承、封装和多态等特性 面向对象基础 面向对象编程&#xff0…
阅读更多...
最新文章

Copyright @ 2022~2023