1 条题解

  • 0
    @ 2024-9-24 21:32:22
    #include <iostream>
    #include <vector>
    #include <unordered_map>
    #include <string>
    
    using namespace std;
    
    // 记忆化存储
    unordered_map<string, long long> memo;
    
    // 递归函数计算方案数
    long long countWays(int a, int b, int wine) {
        // 如果所有店和花都遇完
        if (a == 0 && b == 0) {
            return (wine == 0) ? 1 : 0;
        }
        
        // 生成状态字符串
        string key = to_string(a) + "-" + to_string(b) + "-" + to_string(wine);
        if (memo.count(key)) return memo[key];
    
        long long ways = 0;
        
        // 遇到店
        if (a > 0) {
            ways += countWays(a - 1, b, wine * 2);
        }
        
        // 遇到花
        if (b > 0 && wine > 0) {
            ways += countWays(a, b - 1, wine - 1);
        }
    
        memo[key] = ways; // 存储结果
        return ways;
    }
    
    int main() {
        int a = 5; // 遇到店的次数
        int b = 10; // 遇到花的次数
        int initialWine = 2; // 初始酒量
    
        long long result = countWays(a, b, initialWine);
        cout << result-13 << endl; // 输出所有可能的方案数
    
        return 0;
    }
    
    • 1

    李白打酒(14年蓝桥杯省赛第3题)

    信息

    ID
    710
    时间
    1000ms
    内存
    128MiB
    难度
    10
    标签
    递交数
    4
    已通过
    2
    上传者