数的划分

https://loj.ac/problem/10018

题目描述

　　求把n个整数分为k份，最多有多少种分法（顺序无影响）。

思路

　　这道题是比较典型的dp题，但由于这道题的数据范围比较小，我这里主要想介绍dfs的做法及其剪枝。首先由于我们分解数字不需要顺序，所以我们可以假定分解数的下界为a[i-1]，并且我们已知将数分解a[1],a[2],...,a[i-1],剩余可分解的为m，那么a[i]的最大值为m/(k-i+1),因为剩余的全部平均划分即为a[i]的上界。

代码

#include <bits/stdc++.h>
using namespace std;
int n,m,s=0,a[10];
void dfs(int k)
{
    if(n==0)return ;
    if(k==m)
    {
        if(n>=a[k-1])s++;
        return ;
    }
    for(int i=a[k-1];i<=n/(m-k+1);i++)
    {
        a[k]=i;n-=i;
        dfs(k+1);
        n+=i;
    }
}
int main() 
{
    scanf("%d%d",&n,&m);
    a[0]=1;dfs(1);
    printf("%d",s);
    return 0;
}