当前位置：首页 > article >正文

洛谷题目：P1025 [NOIP2001 提高组] 数的划分题解

article 2025/1/17 7:53:03

题目传送门：P1025 [NOIP2001 提高组] 数的划分 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

解题思路：

1、动态规划：

这道题我们使用动态规划来暴力解决这个问题，定义一个二维数组 $dp[i][j]$ ，表示将证书

$i$ 分成 $j$ 份的不同分法数。

2、状态转移：

状态转移方程为：

$dp[i][j]=dp[i-1][j-1]+dp[i-j][j]$

$dp[i-1][j-1]$ 表示将 $i-1$ 分成 $j-1$ 份，然后每份都加上1.

3、初始化：

$dp[i][1]=1$ 对于所有i>=1，因为将 $i$ 分成 $i$ 份，每份都是1.

4、最终计算结果QWQ：

$dp[n][k]$

5、代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, k;
    cin >> n >> k;

    vector<vector<int>> dp(n + 1, vector<int>(k + 1, 0));

    // 初始化
    for (int i = 1; i <= n; ++i) {
        dp[i][1] = 1; // 将 i 分成 1 份只有一种方法
    }
    for (int j = 1; j <= k; ++j) {
        dp[j][j] = 1; // 将 j 分成 j 份，每份都是 1
    }

    // 动态规划
    for (int i = 2; i <= n; ++i) {
        for (int j = 2; j <= k; ++j) {
            if (i >= j) {
                dp[i][j] = dp[i-1][j-1] + dp[i-j][j];
            }
        }
    }

    // 输出结果
    cout << dp[n][k] << endl;

    return 0;
}

查看全文

http://www.kler.cn/a/506130.html