天池在线编程卡牌游戏（01背包）

Michael阿明

发布于 2021-09-06 02:03:06

38200

代码可运行

文章被收录于专栏：Michael阿明学习之路Michael阿明学习之路

运行总次数：0

代码可运行

1. 题目

你跟你的朋友在玩一个卡牌游戏，总共有 n 张牌。每张牌的成本为 cost[i] 并且可以对对手造成 damage[i] 的伤害。你总共有 totalMoney 元并且需要造成至少 totalDamage 的伤害才能获胜。每张牌只能使用一次，判断你是否可以取得胜利。

样例1
输入:
cost = [1,2,3,4,5]
damage = [1,2,3,4,5]
totalMoney = 10
totalDamage = 10

输出: true
样例说明: 我们可以使用 [1,4,5] 去造成10点伤害，总花费为10。

Example2
输入:
cost = [1,2]
damage = [3,4]
totalMoney = 10
totalDamage = 10

输出: false
样例说明：我们最多只能造成7点伤害。

2. 解题

class Solution {
public:
    /**
     * @param cost: costs of all cards
     * @param damage: damage of all cards
     * @param totalMoney: total of money
     * @param totalDamage: the damage you need to inflict
     * @return: Determine if you can win the game
     */
    bool cardGame(vector<int> &cost, vector<int> &damage, int totalMoney, int totalDamage) {
        // Write your code here
        int n = cost.size();
        unordered_map<int,int> dp;
        dp[0] = 0;
        for(int i = 0; i < n; i++) {
            unordered_map<int,int> tmp(dp.begin(), dp.end());//复制上一次的状态，这次不拿
            for(auto& d : dp) { // 遍历原有状态
                int c = d.first;
                int dg = d.second;
                if(c + cost[i] <= totalMoney)// 可以拿
                {
                    tmp[c + cost[i]] = max(tmp[c+ cost[i]], dg+damage[i]);
                    if(tmp[c + cost[i]] >= totalDamage)
                        return true;
                }
            }
            dp.swap(tmp);
        }
        return false;
    }
};