NOIP 提高组初赛 · NOIP 2017 提高组初赛试题 第 23 题

#include <iostream> 
using namespace std;   
int g(int m, int n, int x)   
{     
    int ans = 0;   
    int i;   
    if (n == 1)  
        return 1;     
    for (i = x; i <= m / n; i++)         
        ans += g(m - i, n - 1, i);     
    return ans; 
} 
int main() 
{     
    int t, m, n;     
    cin >> m >> n;    
    cout << g(m, n, 0) << endl;     
    return 0;   
} 

输入：8 4 输出：_________

看到递归拆分整数 → 先想非降序约束与枚举上界

i 下界误写 0 或 1 破坏非降序；上界误写 m 导致死循环；忘记传 i 作下一层 x。

考点：递归枚举（整数拆分）

程序在做什么

输入 m,n，调用 g(m,n,0) 计算将 m 拆成 n 个非降序正整数的方案数。