首页 > 其他分享 >[NOIP2001 提高组] 数的划分

[NOIP2001 提高组] 数的划分

时间:2024-05-16 21:20:55浏览次数:23  
标签:NOIP2001 int sum 样例 start 划分 include 提高 分法

个人博客传送锚点:https://www.acwing.com/blog/content/55495/
传送锚点:https://www.luogu.com.cn/problem/P1025

题目描述

将整数 $n$ 分成 $k$ 份,且每份不能为空,任意两个方案不相同(不考虑顺序)。

例如:$n=7$,$k=3$,下面三种分法被认为是相同的。

$1,1,5$;
$1,5,1$;
$5,1,1$.

问有多少种不同的分法。

输入格式

$n,k$ ($6<n \le 200$,$2 \le k \le 6$)

输出格式

$1$ 个整数,即不同的分法。

样例 #1

样例输入 #1

7 3

样例输出 #1

4

提示

四种分法为:
$1,1,5$;
$1,2,4$;
$1,3,3$;
$2,2,3$.

思路

这题我们在for循环时还要在进行类似于剪枝优化,如果当前的和 + 剩下的几位数乘i大于n,剪掉就完事,即代码for (int i = start; sum + i * (k - x + 1) <= n; i++)中的sum + i * (k - x + 1) <= n

code

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 205;
int n,k;
int res = 0;//存储方案数
void dfs(int x,int start,int sum) {//x代表当前数字,start代表遍历到第几位
	if (x > k) {
		if(sum == n){
			res ++;
		}
		return;
	}
	for (int i = start; sum + i * (k - x + 1) <= n; i++) {//进行进一步剪枝优化 
	 //k - x  + 1为还要填的数字个数, 
			dfs(x+1, i,sum + i);
	}

}
int main()
{
	cin >> n >> k;
	dfs(1, 1, 0);
	cout << res; 
	return 0;
}

标签:NOIP2001,int,sum,样例,start,划分,include,提高,分法
From: https://www.cnblogs.com/6Luffy6/p/18196745

相关文章

  • Hugging Face 与 Wiz Research 合作提高人工智能安全性
    我们很高兴地宣布,我们正在与Wiz合作,目标是提高我们平台和整个AI/ML生态系统的安全性。Wiz研究人员与HuggingFace就我们平台的安全性进行合作并分享了他们的发现。Wiz是一家云安全公司,帮助客户以安全的方式构建和维护软件。随着这项研究的发布,我们将借此机会重点介绍......
  • 洛谷题单指南-动态规划3-P1063 [NOIP2006 提高组] 能量项链
    原题链接:https://www.luogu.com.cn/problem/P1063题意解读:本质上是一个环形石子合并问题,计算合并产生的最大能量。解题思路:对于环形DP问题,可以把环拆开,并复制2倍长度,然后用1~n的区间长度去枚举1、状态表示设structnode{inthead,tail}用于表示每一个项链节点,其中有头、尾......
  • 如何优化文件跨区域传输的能力,提高市场核心竞争力?
    随着业务的不断扩张和发展,越来越多的企业在异国、异地设立分支机构,用以覆盖更广泛的市场和客户群体,比如医院在不同地域设立一院、二院,企业在不同地域设立分部等等,因此存在必然的文件跨区域传输场景。由于涉及数据在不同网络和区域间的移动,因此需要特别注意安全性和效率。常见的......
  • 如何利用甘特图来提高资源的是使用效率?
    在项目管理中,甘特图是一种常用的工具,用于规划和跟踪项目进度。它通过条形图的形式展示项目的时间表和任务依赖关系,帮助项目经理和团队成员清晰地了解项目的时间线和进度。通过合理利用甘特图,可以显著提高资源的使用效率,确保项目按计划顺利进行。以下是一些具体的策略: 1.明确......
  • n的m划分
    一、问题描述有\(n\)个相同的物品,将它们划分成\(m\)组,有几种划分方法。注:以下划分都算一种:1+1+21+2+12+1+1二、问题简析本题采用动态规划求解。令\(dp[i][j]=\)\(i\)的\(j\)划分的方案数。值得注意的是,本题根据是否可以有\(0\)存在,即允许某一组的......
  • Oracle 删除千万级数据量时,可以考虑以下方法来提高删除效率
    Oracle删除千万级数据量时,可以考虑以下方法来提高删除效率:分批删除:如果需要删除的数据量非常大,可以考虑分批进行删除。sqlDELETEFROMyour_tableWHEREyour_conditionANDrownum<=10000;COMMIT;使用直接路径删除:直接路径删除会绕过常规的SQL解析和绑定,可以减少删除操......
  • 763. 划分字母区间
    给你一个字符串s。我们要把这个字符串划分为尽可能多的片段,同一字母最多出现在一个片段中。注意,划分结果需要满足:将所有划分结果按顺序连接,得到的字符串仍然是s。返回一个表示每个字符串片段的长度的列表。示例1:输入:s="ababcbacadefegdehijhklij"输出:[9,7,8]解释:划......
  • 如何通过汽车制造供应商协同平台,提高供应链的效率与稳定性?
    汽车制造供应商协同是指在汽车制造过程中,整车制造商与其零部件供应商之间建立的一种紧密合作的关系。这种协同关系旨在优化整个供应链的效率,降低成本,提高产品质量,加快创新速度,并最终提升整个汽车产业的竞争力。以下是一些关于汽车制造供应商协同的关键点:供应链管理:汽车制造供应......
  • 机台数据管控怎么做,能够提高效率促进企业快速发展?
    机台数据管控是制造企业信息化管理的重要组成部分,它涉及对生产设备(机台)所产生的数据进行有效的收集、存储、处理和应用。良好的机台数据管控能够帮助企业提高生产效率、降低成本、优化资源配置以及保障生产安全。以下是机台数据管控的几个关键点:数据收集:实时采集机台的运行数据,包......
  • 洛谷 P1031 [NOIP2002 提高组] 均分纸牌 题解
    题目简述有$N$堆纸牌,编号分别为$1,2,\ldots,N$。每堆上有若干张,但纸牌总数必为$N$的倍数。可以在任一堆上取若干张纸牌,然后移动。移牌规则为:在编号为$1$堆上取的纸牌,只能移到编号为$2$的堆上;在编号为$N$的堆上取的纸牌,只能移到编号为$N-1$的堆上;其他堆上取的纸牌,可......