37 条题解
-
0
#include <iostream> #include <vector> using namespace std; const int MAX_N = 50; const int MAX_M = 25; // 记忆化存储表 int memo[MAX_N + 1][MAX_M + 1]; void initializeMemo() { for (int i = 0; i <= MAX_N; ++i) { for (int j = 0; j <= MAX_M; ++j) { memo[i][j] = -1; // -1表示未计算 } } } int countSelections(int n, int m) { // 剪枝条件 if (m == 0) return 1; if (m > (n + 1) / 2) return 0; // 最大可选数量剪枝 if (n <= 0) return 0; if (m == 1) return n; // 选1本的特殊情况 // 检查记忆化表 if (memo[n][m] != -1) { return memo[n][m]; } // 剪枝:如果剩下的书不够选 if (n < 2 * m - 1) { memo[n][m] = 0; return 0; } // 递归计算 int res = countSelections(n - 1, m) + countSelections(n - 2, m - 1); memo[n][m] = res; return res; } int main() { int n, m; cin >> n >> m; // 初始化记忆化表 initializeMemo(); cout << countSelections(n, m) << endl; return 0; }
信息
- ID
- 1
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 1
- 标签
- 递交数
- 4607
- 已通过
- 1304
- 上传者