题面描述
小轩由于见义勇为,他被赠予了光之巨人的变身器!于是小轩变身成为光之巨人,准备去打败入侵地球的怪兽。
这个怪兽血量非常多,总共有mm格血量。
小轩的光之巨人总共会用nn种攻击技能,第ii种攻击技能可以给怪兽造成A i格血的伤害,从而扣除怪兽A i格血量。
当小轩用技能把怪兽的血量扣除到0点以下,他就打败了了怪兽,获得胜利。
然而由于小轩第一次变身,所以任意的技能ii使用之后就会进入超长的冷却,也就是没一个技能只能使用一次。
那么小轩可以获胜吗,如果可以,输出 Yes ,否则输出 No 。
输入格式
第一行输入两个整数mm 、nn,表示怪兽血量为mm,小轩有nn种攻击技能。
接下来第二行输入mm个整数:A 1 ,A 2...... A N,A i表示第ii种技能的伤害值。
输出格式
如果小轩可以获胜,输出 Yes ,否则输出 No 。
输入数据 1
10 3
4 5 6
输出数据 1
Yes
输入数据 2
20 3
4 5 6
输出数据 2
No
![](https://profile-avatar.csdnimg.cn/default.jpg!4)
c++的打怪兽问题!
- 写回答
- 好问题 0 提建议
- 追加酬金
- 关注问题
- 邀请回答
-
1条回答 默认 最新
关注
【以下回答由 GPT 生成】
解决方案
首先,我们可以使用动态规划来解决这个问题。
我们定义一个布尔型的二维数组
dp[m+1][n+1]
,其中dp[i][j]
表示小轩是否能使用前j
个技能将怪兽的血量扣除到i
以下。初始化时,将
dp[0][j]
全设为true
,表示小轩不需要使用任何技能就能将怪兽的血量扣除到0以下。然后,我们可以用一个嵌套循环来遍历
i
从1到m
,j
从1到n
,并根据当前技能的伤害值判断小轩是否能够使用该技能:- 如果小轩可以使用当前技能,则有两种情况:
- 使用当前技能,将怪兽的血量扣除到
i-A[j-1]
以下; - 不使用当前技能,保持怪兽的血量不变。
在这两种情况下,只要有一种情况小轩能够胜利,则将
dp[i][j]
设为true
。 - 如果小轩不可以使用当前技能,则继续保持
dp[i][j]
的值为false
。
在循环结束后,如果
dp[m][n]
的值为true
,则小轩能够获胜,输出"Yes";否则,输出"No"。下面是具体的C++代码实现:
#include <iostream> #include <vector> using namespace std; string canDefeatMonster(int m, int n, vector<int>& A) { vector<vector<bool>> dp(m+1, vector<bool>(n+1, false)); // 初始化 for (int j = 0; j <= n; j++) { dp[0][j] = true; } // 动态规划 for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (i >= A[j-1]) { dp[i][j] = dp[i][j-1] || dp[i-A[j-1]][j-1]; } else { dp[i][j] = dp[i][j-1]; } } } if (dp[m][n]) { return "Yes"; } else { return "No"; } } int main() { int m, n; cin >> m >> n; vector<int> A(n); for (int i = 0; i < n; i++) { cin >> A[i]; } string result = canDefeatMonster(m, n, A); cout << result << endl; return 0; }
复杂度分析:
该算法使用了一个二维数组来存储中间结果,时间复杂度为O(mn),空间复杂度也为O(mn)。在整个算法过程中,只使用了一个二维数组来存储结果,没有使用额外的空间。
【相关推荐】
- 这个问题的回答你可以参考下: https://ask.csdn.net/questions/7548335
- 这篇博客你也可以参考下:C++抽象类的使用问题!
- 您还可以看一下 陈小玉老师的C++快速入门课程中的 函数小节, 巩固相关知识点
- 除此之外, 这篇博客: C++函数中的 递归的问题 部分也许能够解决你的问题。
如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^本回答被题主选为最佳回答 , 对您是否有帮助呢?解决 1无用 1
悬赏问题
- ¥100 用数字代替ip主机号断与旋转链接号段
- ¥20 学校内手机热点不能使用
- ¥15 qwen模型微调训练时grad_norm为0.0或为nan
- ¥15 若依- Spring cloud-plus集成阿里云schedulerX再控制台应用管理找不到实例
- ¥15 用vs2022 fortran调试只无法查看数组的值,显示发生未指定的错误
- ¥50 SGD Gateway 是否可以与 SGD Server 装在一台服务器上?
- ¥15 gge梦幻西游的地图制作
- ¥15 对计算机的学习没有方向
- ¥15 用VBA抓取淘宝的发票号码和下载发票pdf遇到的问题
- ¥20 java excel导出有什么解决方案