P1025 数的划分

admin

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

在没有办法的时候我们可以说深搜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)不要搜索，直接算出来比较好。

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. const int maxm=201;
   
4. const int maxn=7;
   
5. int n,k,ans=0;
   
6. int a[maxn];
   
7. void mysearch(int i,int s)  //枚举第i个数
   
8. {
   
9.         int j;
   
10.         if (i>=k)
    
11.                 {
    
12.                         a[k]=s;  //计算出A[k]而不是枚举出a[k]，减少一次递归，
    
13.                         if (a[k]>=a[k-1])
    
14.                                 {
    
15.                                         ++ans;
    
16.                                         /*cout<<setw(5)<<ans<<':';
    
17.                                         for (int p=1; p<=k; p++) cout<<a[p]<<' ';
    
18.                                         cout<<endl;
    
19.                                         */
    
20.                                 }
    
21.                 }
    
22.         else for (j=a[i-1]; j*(k-i+1)<=s; j++)
    
23.                         {
    
24.                                 a[i]=j;
    
25.                                 mysearch(i+1,s-j);
    
26.                         }
    
27. 
    
28. }
    
29. int main()
    
30. {
    
31.         cin>>n>>k;
    
32.         a[0]=1;
    
33.         mysearch(1,n);
    
34.         cout<<ans;
    
35.         return 0;
    
36. }
    

复制代码

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

admin

还有一个做法就是经典的数的划分模型，这个是基本的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)。照此递推就是。

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

复制代码