洛谷 P1025 数的划分

// 第 ① 版：每一份都从 1 开始枚举 —— 它数的是「有顺序的分法」
//
// 最直白的翻译：递归 k 层，第 j 层决定第 j 份分多少，最后一份用掉剩下的全部。
// ⚠ 而它把 `1,1,5`、`1,5,1`、`5,1,1` 当成三种分法 —— 题目明说这三种**是同一种**。
//
// ★ 这一处**样例就能挡住**：n = 7、k = 3 的正确答案是 4，它给 15。
//
// 输入：一行两个整数 n 和 k。

#include <bits/stdc++.h>
using namespace std;

int n, k;
long long ans = 0, calls = 0;

/** 已经分了 cnt 份，还剩 rest 要分完 */
void dfs(int cnt, int rest) {
    calls++;
    if (cnt == k - 1) {             // 只剩最后一份了：它就是剩下的全部
        if (rest >= 1) ans++;
        return;
    }
    for (int x = 1; rest - x >= k - cnt - 1; x++)   // ⚠ 从 1 开始，没有「不小于上一份」这个限制
        dfs(cnt + 1, rest - x);
}

int main(int argc, char** argv) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> k;
    dfs(0, n);
    cout << ans << '\n';
    if (argc > 1 && string(argv[1]) == "calls") cerr << "dfs 调用了 " << calls << " 次\n";
    return 0;
}

// 第 ② 版（推荐写法）：每一份都不小于上一份 —— 一句话去掉全部重复
//
// ★ 关键的一步：**不考虑顺序，就等于「只数不下降的那一种排法」**。
//   `1,1,5` / `1,5,1` / `5,1,1` 里只有 `1,1,5` 是不下降的，
//   所以只要规定「这一份 ≥ 上一份」，每组数就恰好被数到一次。
//   （和 [P1157 组合的输出](/sol/p1157) 是同一件事：排列 → 组合，只改 for 的起点。）
//
// ⚠ 循环的上界那一句也要想清楚：这一份取 x 之后还剩 rest − x、还要分 k − cnt − 1 份，
//   而每一份都不小于 x ⇒ 只有 (k − cnt − 1) × x ≤ rest − x 时才走得下去。
//   ★ 这一条剪枝不是「优化」，它是**正确性的一部分**在效率上的顺带好处 ——
//   没有它，n = 200、k = 6 要多跑 20 多倍（正文第 ④ 步有实测）。

#include <bits/stdc++.h>
using namespace std;

int n, k;
long long ans = 0, calls = 0;

/** 已经分了 cnt 份，上一份是 last，还剩 rest */
void dfs(int cnt, int last, int rest) {
    calls++;
    if (cnt == k - 1) {             // 只剩最后一份了：它就是剩下的全部
        if (rest >= last) ans++;    // ⚠ 它也要 ≥ 上一份，否则这组数根本不是不下降的
        return;
    }
    for (int x = last; (long long)(k - cnt - 1) * x <= rest - x; x++)
        dfs(cnt + 1, x, rest - x);
}

int main(int argc, char** argv) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> k;
    dfs(0, 1, n);
    cout << ans << '\n';
    if (argc > 1 && string(argv[1]) == "calls") cerr << "dfs 调用了 " << calls << " 次\n";
    return 0;
}

// 第 ③ 版：不搜了，直接递推 —— O(nk) 个格子
//
// ★ 设 f[i][j] = 把 i 分成 j 份（每份 ≥ 1，不计顺序）有几种。分两类，不重不漏：
//
//     · 至少有一份是 1  ⇒ 把那个 1 拿掉，剩下的是「i−1 分成 j−1 份」  ⇒ f[i-1][j-1]
//     · 每一份都 ≥ 2    ⇒ 每份都减 1，变成「i−j 分成 j 份」            ⇒ f[i-j][j]
//
//     f[i][j] = f[i-1][j-1] + f[i-j][j]
//
// ⚠ 第二类为什么不会和第一类重：第一类里**至少有一个 1**，第二类里**一个 1 都没有**。
//   ★ 这种「按有没有 1 分家」的拆法，和第 24 章背包「选不选第 i 件」是同一个套路。
//
// 边界：f[0][0] = 1（什么都不分，算一种）；i < j 时是 0（每份至少 1，分不出那么多份）。

#include <bits/stdc++.h>
using namespace std;

long long f[205][10];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    cin >> n >> k;
    f[0][0] = 1;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= k; j++) {
            f[i][j] = f[i - 1][j - 1];
            if (i >= j) f[i][j] += f[i - j][j];
        }
    cout << f[n][k] << '\n';
    return 0;
}

// 换一把尺子：三种写法各自「碰了多少下」
//
//   ① 每份从 1 起枚举（数的是有顺序的分法）—— dfs 调用次数
//   ② 每份不小于上一份                      —— dfs 调用次数
//   ③ 递推                                  —— 填了多少个格子（固定 n × k）
//
// ★ 正文第 ④ 步那张表就是它打的。用法：./p1025Count <n> <k> [csv]

#include <bits/stdc++.h>
using namespace std;

int n, k;
long long callsA = 0, ansA = 0, callsB = 0, ansB = 0;

void dfsA(int cnt, int rest) {
    callsA++;
    if (cnt == k - 1) { if (rest >= 1) ansA++; return; }
    for (int x = 1; rest - x >= k - cnt - 1; x++) dfsA(cnt + 1, rest - x);
}
void dfsB(int cnt, int last, int rest) {
    callsB++;
    if (cnt == k - 1) { if (rest >= last) ansB++; return; }
    for (int x = last; (long long)(k - cnt - 1) * x <= rest - x; x++) dfsB(cnt + 1, x, rest - x);
}

int main(int argc, char** argv) {
    n = (argc > 1) ? atoi(argv[1]) : 7;
    k = (argc > 2) ? atoi(argv[2]) : 3;
    bool csv = (argc > 3 && string(argv[3]) == "csv");
    dfsA(0, n);
    dfsB(0, 1, n);
    long long cells = (long long)n * k;
    if (csv) {
        cout << "ordered," << ansA << '\n';
        cout << "answer," << ansB << '\n';
        cout << "callsA," << callsA << '\n';
        cout << "callsB," << callsB << '\n';
        cout << "cells," << cells << '\n';
    } else {
        cout << "n = " << n << "，k = " << k << '\n';
        cout << "① 每份从 1 起（有顺序）  答案 " << ansA << "，dfs 调用 " << callsA << " 次\n";
        cout << "② 每份不小于上一份        答案 " << ansB << "，dfs 调用 " << callsB << " 次\n";
        cout << "③ 递推                    答案同上，只填了 " << cells << " 个格子\n";
    }
    return 0;
}