题解 | #[NOIP2001]数的划分#

2021.11.18

本题可以参照题解，递增的序列，如果不是严格递增，就进行回溯，每次递归n/k是为了保证重复的序列只出现一次，所以进行取半。 案例所给的意思可以理解为如下 最后一个要选的数其实已经被之前k-1个数确定了，不用去规划了。

#include<iostream>
#include<cstring>
const int N = 1e9 + 7;
using namespace std;
int n,k,num = 0;
void dfs(int n,int k,int i){
    if(k == 1) {
        num++;
        return;
    }
    for(int j = 1;j<=n/k;j++){
        if(j>=i){
            dfs(n-j,k-1,j);
        }
    } 
}
int main(){
    cin >> n >>k;
    dfs(n,k,0);
    cout << num;
    return 0;
}