ACM 训练日志记录 · 思考 · 成长
提交 / 修改记录
王梓豪 / 题目列表训练档案
导出

P1025　数的划分

来源：洛谷 ★ 1300

DFS
本题活力0.26按难度、完成结果与训练证据估算

算法如山行则将至

查看原题王梓豪 的主页

题目描述

将整数 n 分成 k 份，且每份不能为空，任意两个方案不相同（不考虑顺序）。

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

1,1,5；
1,5,1；
5,1,1。

问有多少种不同的分法。

代码

#include <bits/stdc++.h>
using namespace std;
int ans=0;
void dfs(int last,int cnt,int rest)
{
    if(cnt==1)
    {
        if(rest>=last)
        ans++;
    }
    else if(cnt>1)
    {
        for(int i=last;i<=rest-cnt+1;i++)
        {
            dfs(i,cnt-1,rest-i);
        }
    }
}
int main() {
    int n,k;
    cin>>n>>k;
    dfs(1,k,n);
    cout<<ans;
}