华师一附中OI组

标题: P1025 数的划分 [打印本页]

作者: admin 时间: 2020-3-14 17:53
标题: P1025 数的划分
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≤200，2≤k≤6)

输出格式
1个整数，即不同的分法。

输入输出样例
输入 #1复制
7 3
输出 #1复制
4
说明/提示
四种分法为：
1,1,5;
1,2,4;
1,3,3;
2,2,3.

作者: admin 时间: 2021-5-13 18:33
在没有办法的时候我们可以说深搜DFS。但是整体的DFS还是很有技巧的。假设n=a(1)+a(2)+a(3)+**a(k)，按照题目的要求，因为a(1)<=a(2)<=a(3)<=*a(k),那么a(1)<=n/k,a(2)<=n/(k-1)****,最后一个a(k)不要搜索，直接算出来比较好。

#include <bits/stdc++.h>
using namespace std;
const int maxm=201;
const int maxn=7;
int n,k,ans=0;
int a[maxn];
void mysearch(int i,int s) //枚举第i个数
{
int j;
if (i>=k)
{
a[k]=s; //计算出A[k]而不是枚举出a[k]，减少一次递归，
if (a[k]>=a[k-1])
{
++ans;
/*cout<<setw(5)<<ans<<':';
for (int p=1; p<=k; p++) cout<<a[p]<<' ';
cout<<endl;
*/
}
}
else for (j=a[i-1]; j*(k-i+1)<=s; j++)
{
a[i]=j;
mysearch(i+1,s-j);
}
}
int main()
{
cin>>n>>k;
a[0]=1;
mysearch(1,n);
cout<<ans;
return 0;
}

复制代码

体会下这个search(i,s)。学习下这种把s带进去的做法，以后会经常用到。

作者: admin 时间: 2021-5-13 18:40
还有一个做法就是经典的数的划分模型，这个是基本的Dp或者递推。用f(n,k)表示把n分成k个数的和的分法，那么这种分法可以有两类：
A、仅仅含有一个数字1，就是第一个
B、所有的数字都大于1
这两个集合是互不重叠，不可能有一种分法既属于A也属于B ，另外，某种分法不是A就是B。所以他们互为补集。
A可以理解为第一个数是1，那么等价于f(n-1,k-1)。剩下的n-1分成k-1份
B可以理解为f(n-k,k)；因为每个数字都大于1，若每个数字都减1的话就等价于n-k分成了k分。
所以f(n,k)=f(n-1,k-1)+f(n-k,k)。照此递推就是。

for(i=1;i<=maxm;i++) {d[i][1]=1; //任何数字分成1个数字有一种做法；
d[i][2]=i/2;}//任何数字分成2个数字有i/2种做法；
for(i=2;i<=maxm;i++)
for(j=2;j<=maxn-1;j++)
if (i>=j) d[i][j]=d[i-1][j-1]+d[i-j][j];

复制代码

欢迎光临华师一附中OI组 (http://hsyit.cn/)