02022 - 蓝桥云课
2022
问题描述
---------
将2022拆分成10个互不相同的正整数之和，总共有多少种拆分方法？
注意交换顺序视为同一种方法，例如2022 = 1000 + 1022 和 2022 = 1022 + 1000 就视为同一种方法。
答案提交
---------
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
运行限制
---------
- 最大运行时间：1s
- 最大运行内存：512M
总通过次数：4542 | 总提交次数：5214 | 通过率：87.1%
难度：中等 标签：2022，国赛，背包问题
版权声明
---------
思路：
背包问题
记忆化搜索：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// 记忆化数组：memo[i][j][k]表示前i个数中选j个数，和为k的方案數
ll memo[2022 + 1][10 + 1][2022 + 1];ll dfs(ll i, ll j, ll k)
{// 边界条件处理if (j < 0 || k < 0) return 0; // 非法状态if (j == 0 && k == 0) return 1; // 恰好选够且和为0（合法方案）if (i == 0) return 0; // 没有数可选但未满足条件if (memo[i][j][k] != -1) return memo[i][j][k];ll res = 0;res = dfs(i - 1, j, k); // 不选第i个数的情况// 选第i个数的情况（需满足k >= i且j至少选1個）if (k >= i && j >= 1) {res = dfs(i - 1, j, k) + dfs(i - 1, j - 1, k - i);}return memo[i][j][k] = res;
}int main()
{memset(memo, -1, sizeof(memo));cout << dfs(2022, 10, 2022);return 0;
}dp：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll f[2023][11][2023];
int main()
{for (ll i = 0; i <= 2022; i++) //因为体积为0，物品为0的所有情况都只有一种选择，即什么都不选f[i][0][0] = 1;for (ll i= 1; i <= 2022; i++) //枚举所有物品{for (ll j = 1; j <= 10; j++) //选了几个物品{for (ll k = 1; k <= 2022; k++) //枚举体积{if (k >= i && j >= 1) //选第i个物品f[i][j][k] += f[i-1][j - 1][k - i] + f[i-1][j][k];elsef[i][j][k] = f[i-1][j][k]; //不选第i个物品}}}cout << f[2022][10][2022];return 0;
}
