2025年整数划分

科技前沿 • 2025-03-23 22:14 • 阅读 52

大家好，我是讯享网，很高兴认识大家。

将整数 nn 分成 kk 份，且每份不能为空，任意两个方案不相同(不考虑顺序)。

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

1,1,51,1,5 ;
1,5,11,5,1 ;
5,1,15,1,1 .

问有多少种不同的分法。

输入输出格式

输入格式：

n,kn,k ( 6<n \le 2006<n≤200 ， 2 \le k \le 62≤k≤6 )

输出格式：

11 个整数，即不同的分法。

输入输出样例

输入样例#1： 复制

7 3

讯享网

输出样例#1： 复制

讯享网4

说明

四种分法为：
1,1,51,1,5 ;
1,2,41,2,4 ;
1,3,31,3,3 ;
2,2,32,2,3 .

讯享网

这题其实是排列组合里的题，可以把一个数值为n的数当做n个小球，划分的份数k当做k个盒子，那么本题可以转化为“将n个小球放到k个盒子中，小球之间与盒子之间没有区别，并且最后的结果不允许空盒”

将n个小球放到k个盒子中的情况总数 =

a.至少有一个盒子只有一个小球的情况数

+b.没有一个盒子只有一个小球的情况数

这样进行划分是因为这种分类可以使a和b都有能写出来的表达式：

a.因为盒子不加区分，那么1的情况数与“将n-1个小球放到k-1个盒子中”的情况数一样

b.没有一个盒子只有一个小球，那么把每个盒子中拿出来一个小球，对应的是“把(n-k)个小球放到k个盒子中的情况数”

然后将上面的思路化为动态转移方程：

设f[n,k]代表将n个小球放到k个盒子中且没有空盒的情况，那么f[n,k] = f[n-1,k-1] + f[n-k,k]

而当k=1时只有1种方法(小球全部放进1个盒子)

所以可得:

#include<bits/stdc++.h> using namespace std; int n,k,f[201][7]; //f[k][x] k 分成 x 份 ={f[k-1][x-1],f[k-x][x]} int main(){ cin >> n >> k; for (int i=1;i<=n;i++) {f[i][1]=1;f[i][0]=1;}for (int x=2;x<=k;x++) {f[1][x]=0;f[0][x]=0;} // 边界，为了防止炸，我把有0的也处理了 for (int i=2;i<=n;i++) for (int x=2;x<=k;x++) if (i>x) f[i][x]=f[i-1][x-1]+f[i-x][x]; else f[i][x]=f[i-1][x-1]; cout<<f[n][k]; return 0; }

下面是dfs做法：

这里因为要考虑到不重复，所以可以按升序记录每一次划分：记录上一次划分所用的数，保证当前划分所用数不小于上次划分所用分数，当划分次数等于k时比较该次划分所得总分是否与n相同并记录次数。

有一个不得不做的剪枝就是枚举当前划分所用分数时应该从last(上次划分所用分数)枚举到sum+i*(k-cur)<=n为止，因为之后划分的分数一定大于或等于当前划分所用分数。

讯享网#include<cstdio> int n,k,cnt; void dfs(int last,int sum,int cur) { if(cur==k) { if(sum==n) cnt++; return; } for(int i=last;sum+i*(k-cur)<=n;i++)//剪枝，只用枚举到sum+i*(k-cur)<=n为止，这是保证存在下一个大于i的数， dfs(i,sum+i,cur+1); } int main() { scanf("%d%d",&n,&k); dfs(1,0,0); printf("%d",cnt); }

2025年整数划分

输入输出格式

输入输出样例

说明

相关推荐