文章目錄

• • 1. 題目
  • 2. 解題

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點傷害。

https://tianchi.aliyun.com/oj/286614371019772507/338469151696950134

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 hereint 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++

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！

總結

以上是生活随笔為你收集整理的天池 在线编程 卡牌游戏（01背包）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。