你跟你的朋友在玩一个卡牌游戏,总共有 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点伤害。
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;
}
};
100ms C++
扫码关注腾讯云开发者
领取腾讯云代金券
Copyright © 2013 - 2025 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号:粤B2-20090059 深公网安备号 44030502008569
腾讯云计算(北京)有限责任公司 京ICP证150476号 | 京ICP备11018762号 | 京公网安备号11010802020287
Copyright © 2013 - 2025 Tencent Cloud.
All Rights Reserved. 腾讯云 版权所有