Loading [MathJax]/jax/output/CommonHTML/config.js
前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
社区首页 >专栏 >天池 在线编程 卡牌游戏(01背包)

天池 在线编程 卡牌游戏(01背包)

作者头像
Michael阿明
发布于 2021-09-06 02:03:06
发布于 2021-09-06 02:03:06
34700
代码可运行
举报
运行总次数:0
代码可运行

1. 题目

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

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
样例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. 解题

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
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++

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

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2021/02/27 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
牛客 牛牛选物(01背包)
链接:https://ac.nowcoder.com/acm/contest/9887/A 来源:牛客网
Michael阿明
2021/02/19
4120
牛客 牛牛选物(01背包)
天池 在线编程 最小的行程(动态规划)
https://tianchi.aliyun.com/oj/338592228998370026/357527484118536805
Michael阿明
2021/09/06
2690
天池 在线编程 安排面试城市(贪心)
来源:https://tianchi.aliyun.com/oj/210874425247820050/215397455965131520
Michael阿明
2021/02/19
3400
天池 在线编程 高效作业处理服务(01背包DP)
https://tianchi.aliyun.com/oj/231188302809557697/235445278655844967
Michael阿明
2021/02/19
3220
天池 在线编程 高效作业处理服务(01背包DP)
天池 在线编程 回合制游戏(前缀和)
QW 在一场战斗中会碰到 n 个怪物,每个怪物有攻击力 atk[i],每回合结束时如果第 i 个怪物还活着,就会对 QW 造成 atk[i] 的伤害。 QW 只能在每回合开始时击杀一个怪物,请帮 QW 出他打完所有怪物最少需要损失多少生命值。
Michael阿明
2021/02/19
3130
天池 在线编程 回文子串(区间动态规划)
回文串是从左往右和从右往左读相同的字符串,例如121和tacocat。子串是一个字符串中任意几个连续的字符构成的字符串。
Michael阿明
2021/09/06
2430
天池 在线编程 部门统计(哈希)
描述 公司给你提供了所有员工的信息,包括其ID,姓名和所属部门。 以及他们之间的朋友关系,每个关系中由2个ID组成,如 “1, 2” 代表1号员工和2号员工是朋友。 朋友关系不具有传递性,即B、C都是A的朋友,但B和C不一定是朋友。 请计算每个部门中与其它部门的员工有朋友关系的员工个数。
Michael阿明
2021/09/06
3730
LeetCode 周赛题解 211
遍历字符串,记录每个字符第一次出现的位置。当某个字符再次出现时,说明找到了相同的两个字符,那就更新一下最大长度。
ACM算法日常
2020/10/30
4760
LeetCode 周赛题解 211
天池 在线编程 聪明的销售(计数+贪心)
现在她知道她最多能删除多少物品,她想知道最终袋子里最少可以包含多少种不同编号的物品。
Michael阿明
2021/02/19
2470
天池 在线编程 放小球(动态规划)
n 个桶中小球的个数已知, 可以操作 k 次(每次从桶中取出一个球,或者添加一个球), 每个桶有规定的最大容量 W[i]。 求操作后两相邻桶之间的最大差值的平方的最小值。
Michael阿明
2021/02/19
3490
【LeetCode 周赛】一道 01 背包变型题
由于题目要求相邻元素之间至少存在单向整除关系,容易想到我们需要预处理数据,记录每个元素在作为 (x, y) 相邻对中的 x 时,下一个数 y 可以选择什么数,即从 x 到 y 存在单向边。
用户9995743
2023/09/09
2500
【LeetCode 周赛】一道 01 背包变型题
天池 在线编程 最频繁出现的子串(字符串哈希)
子串的长度在之间 [minLength, maxLength] 子串的字符种类不超过 maxUnique 写一个函数 getMaxOccurrences ,其返回满足条件的子串最多出现次数。
Michael阿明
2021/02/19
5650
天池 在线编程 最频繁出现的子串(字符串哈希)
天池 在线编程 旅行计划(暴力回溯)
描述 有n个城市,给出邻接矩阵arr代表任意两个城市的距离。 arr[i][j]代表从城市i到城市j的距离。Alice在周末制定了一个游玩计划,她从所在的0号城市开始,游玩其他的1 ~ n-1个城市,最后回到0号。 Alice想知道她能完成游玩计划需要行走的最小距离。返回这个最小距离。除了城市0之外每个城市只能经过一次。
Michael阿明
2021/02/19
2750
LeetCode 第 207 场周赛(245/4115,前5.95%)
全国排名: 245 / 4115,5.95%;全球排名: 774 / 12923,5.99%
Michael阿明
2021/02/19
3870
天池 在线编程 课程表(拓扑排序 + 回溯)
总共有n个课程,从0到n-1。 有些课程可能有先决条件,例如,你想修课程0,你必须先修一门课程1,这两门课之间的关系表示为:[0,1]
Michael阿明
2021/09/07
4680
天池 在线编程 数组游戏
样例 1 输入: [3, 4, 6, 6, 3] 输出: 7 说明: [3, 4, 6, 6, 3] -> [4, 5, 7, 6, 4] -> [5, 6, 7, 7, 5] -> [6, 7, 8, 7, 6] -> [7, 8, 8, 8, 7] -> [8, 9, 9, 8, 8] -> [9, 9, 10, 9, 9] -> [10, 10, 10, 10, 10]
Michael阿明
2021/02/19
6030
天池 在线编程 数组游戏
使用c++SFML制作月圆之夜总集篇[通俗易懂]
重新以时间线的形式整理一下去年使用c++的SFML库制作月圆之夜(游戏程序设计大作业)的开发过程,括号里面是新的补充以及对一年前自己的吐槽
全栈程序员站长
2022/11/17
3.4K0
使用c++SFML制作月圆之夜总集篇[通俗易懂]
【代码随想录】二刷-贪心算法
贪心算法 什么是贪心? 贪心的本质是选择每一阶段的局部最优,从而达到全局最优。 贪心没有规定的套路。 刷题或面试的时候,手动模拟一下感觉可以局部最优退出整体最优,而且想不到反例,那么就试一试贪心。 贪心算法一般分为如下四步: 将问题分为若干子问题 找出合适的贪心策略 求解每一个子问题的最优解 将局部最优解堆叠成全局最优解 ---- 455. 分发饼干 方法1: 充分利用每个饼干的大小,用大块的饼干优先喂饱大胃口的孩子 class Solution { public:
半生瓜的blog
2023/05/13
4300
【代码随想录】二刷-贪心算法
【代码随想录】二刷-动态规划
动态规划 解题步骤: 确定dp数组 确定递推公式——递推公式决定dp数组要如何初始化 dp数组如何初始化 确定遍历顺序 举例推导dp数组 ---- 509. 斐波那契数 class Solution { public: int fib(int n) { if(n <= 1)return n; // 推导公式: dp[n] = dp[n-1]+dp[n-2] int dp[2]; // 初始化 dp[0] =
半生瓜的blog
2023/05/13
4940
【算法/训练】:动态规划DP
动态规划(Dynamic Programming,DP)是一种在数学、管理科学、计算机科学、经济学和生物信息学等领域中使用的,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题
IsLand1314
2024/10/15
4050
【算法/训练】:动态规划DP
推荐阅读
相关推荐
牛客 牛牛选物(01背包)
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档
查看详情【社区公告】 技术创作特训营有奖征文
本文部分代码块支持一键运行,欢迎体验
本文部分代码块支持一键运行,欢迎体验