37 条题解

  • 0
    @ 2025-7-22 16:08:35
    #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
    上传者