免费网站你懂我意思正能量软件,网站制作难度,企业网络推广方案模板,网站设计公司 无锡米哈游20230924秋招T2-米小游与魔法少女-奇运
题目描述与示例
题目描述
米小游都快保底了还没抽到希儿#xff0c;好生气哦#xff01;只能打会活动再拿点水晶。
米小游和世界第一可爱的魔法少女 TeRiRi 正在打 BOSS#xff0c;BOSS 的血量为h#xff0c;当 BOSS 血量小…米哈游20230924秋招T2-米小游与魔法少女-奇运
题目描述与示例
题目描述
米小游都快保底了还没抽到希儿好生气哦只能打会活动再拿点水晶。
米小游和世界第一可爱的魔法少女 TeRiRi 正在打 BOSSBOSS 的血量为h当 BOSS 血量小于等于0时BOSS 死亡。TeRiRi 有一套牌在一轮中她会按顺序一张一张的将卡牌打出套牌中有两种卡牌
时来运转获得x个幸运币。幸运一掷造成x点伤害并投掷所有幸运币造成等于所有幸运币掷出的点数之和的伤害。
幸运币可以等概率的投掷出1∼6之间的点数。 所以为什么不叫骰子呢
米小游想知道TeRiRi 的套牌在一轮内击杀 BOSS 的概率。
输入描述
第一行输入两个整数n (1≤n≤100)h (1≤h≤10^9)分别表示卡牌张数和 BOSS 血量。
接下来n行每行首先输入两个整数t (1≤t≤2)x (1≤x≤10)t为1表示卡牌为时来运转t为2表示卡牌为幸运一掷。
输出描述
输出一个实数表示答案你的答案与标准答案的误差不超过10^−4都被认为是正确答案。
示例一
输入
2 5
1 1
2 1输出
0.5说明
幸运币掷出4及以上的概率为0.5再加上1点固定伤害即可击杀BOSS。
示例二
输入
3 1145
1 4
1 9
1 9输出
0说明
无论如何都无法击杀BOSS。
解题思路
对于固定顺序的套牌投掷幸运币的数量是固定的。这里要注意的是由于时来运转之后必须接上幸运一掷才能将幸运币打出造成伤害所以如果最后的若干张连续的卡牌是时来运转这些最后获得的幸运币也是无法造成伤害的。
我们将造成的伤害分为两部分固定伤害和随机伤害前者为打出y个幸运币必定造成的z点伤害后者为y个幸运币掷出点数和的伤害。
假设整套卡牌一共投掷了y个幸运币造成的固定伤害为z点如果想要击杀BOSS随机伤害必须至少达到h-z点才可以。当然如果h-z≤0则必定可以击杀BOSS。
问题就转换为投掷出y个幸运币点数总和超过h-z的概率是多少
由于每一个幸运币都是独立的在掷出第i个幸运币时其结果是从掷出第i-1个幸运币时得到的各种结果转移得到的因此我们可以使用动态规划来解决该问题。我们考虑动态规划三部曲
dp数组的含义是什么
dp数组是一个长度为(y1)×(h-z1)的二维矩阵dp[i][j]表示掷出第i个幸运币时有多大的概率可以取得和为j的结果即造成和为j的伤害。特别地由于只需要判断伤害之和大于等于h-z的概率而不用关心具体的分布dp数组内层的第h-z个元素即dp[i][h-z]表示求和大于等于h-z的概率。
动态转移方程是什么
由于幸运币掷出点数1-6是等概率的故对于某一个特定的dp[i-1][j]在掷出第i个幸运币时dp[i-1][j]的结果将等概率地转换到dp[i][j1]dp[i][j2]dp[i][j3]dp[i][j4]dp[i][j5]dp[i][j6]即每一个状态都可以取得1/6的转移。另外如果jk之后超过了h-z则将直接获得(7-k)/6 * dp[i-1][j]的概率。
for i in range(1, y1):for j in range(i-1, h-z1):for k in range(1, 7):if j k h - z:dp[i][h-z] (7-k)/6 * dp[i-1][j]breakelse:dp[i][jk] 1/6 * dp[i-1][j]dp数组如何初始化
考虑不投掷任何幸运币的情况那么只有一种情况也就是在投掷0个幸运币的时候获得求和为0的概率为恒定1。故初始化dp[0][0] 1
dp [[0] * (h-z1) for _ in range(y1)]
dp[0][0] 1考虑完上述问题后代码其实呼之欲出了。
代码
Python
# 题目【DP】米哈游2023秋招-米小游与魔法少女-奇运
# 作者闭着眼睛学数理化
# 算法DP
# 代码有看不懂的地方请直接在群上提问y 0 # 掷出幸运币的总个数
z 0 # 全部造成的固定伤害
x_temp 0 # 时来运转获得的幸运币n, h map(int, input().split())
for _ in range(n):t, x map(int, input().split())# 时来运转if t 1:x_temp x# 幸运一掷else:y x_tempx_temp 0z x# 如果固定伤害已经大于h直接输出1
if h - z 0:print(1)
# 否则才需要进行dp过程
else:# 初始化dp数组# dp[i][j]表示掷出了i个幸运币时# 有多大的概率可以取得和为j的结果即造成和为j的伤害。dp [[0] * (h-z1) for _ in range(y1)]dp[0][0] 1# 考虑每一个幸运币for i in range(1, y1):# 对于每一个幸运币考虑打出i-1个硬币后的# 每一种求和结果的概率# 注意由于已经掷出了i-1个幸运币# 那么求和结果至少为i-1因为每个幸运币点数至少为1点# 因此j遍历时起点可以从i-1开始for j in range(i-1, h-z1):# 如果求和j尚未在上一次投掷中取得# 则可以直接考虑下一个幸运币if dp[i-1][j] 0:break# 遍历掷出六种不同点数k的情况# 当前点数则可以取得jkfor k in range(1, 7):# 如果当前点数jk超过了击杀所需点数# 则更新dp[i][h-z]# 为dp[i-1][j]对应的概率乘以(7-k)/6if j k h - z:dp[i][h-z] (7-k)/6 * dp[i-1][j]break# 如果当前点数jk尚未超过击杀所需点数# 则其概率由dp[i-1][j]六等分后转移得到else:dp[i][jk] 1/6 * dp[i-1][j]# 输出最后一行的最后一个元素# 表示打出第y个幸运币后造成伤害大于等于h-z点的概率print(dp[y][h-z])Java
import java.util.Scanner;public class Main {public static void main(String[] args) {int y 0; // 掷出幸运币的总个数int z 0; // 全部造成的固定伤害int x_temp 0; // 时来运转获得的幸运币Scanner scanner new Scanner(System.in);int n scanner.nextInt();int h scanner.nextInt();for (int i 0; i n; i) {int t scanner.nextInt();int x scanner.nextInt();// 时来运转if (t 1) {x_temp x;}// 幸运一掷else {y x_temp;x_temp 0;z x;}}// 如果固定伤害已经大于h直接输出1if (h - z 0) {System.out.println(1);}// 否则才需要进行dp过程else {// 初始化dp数组// dp[i][j]表示掷出了i个幸运币时// 有多大的概率可以取得和为j的结果即造成和为j的伤害。double[][] dp new double[y 1][h - z 1];dp[0][0] 1.0;// 考虑每一个幸运币for (int i 1; i y; i) {// 对于每一个幸运币考虑打出i-1个硬币后的// 每一种求和结果的概率// 注意由于已经掷出了i-1个幸运币// 那么求和结果至少为i-1因为每个幸运币点数至少为1点// 因此j遍历时起点可以从i-1开始for (int j i - 1; j h - z; j) {// 如果求和j尚未在上一次投掷中取得// 则可以直接考虑下一个幸运币if (dp[i - 1][j] 0) {break;}// 遍历掷出六种不同点数k的情况// 当前点数则可以取得jkfor (int k 1; k 6; k) {// 如果当前点数jk超过了击杀所需点数// 则更新dp[i][h-z]// 为dp[i-1][j]对应的概率乘以(7-k)/6if (j k h - z) {dp[i][h - z] (7 - k) / 6.0 * dp[i - 1][j];break;}// 如果当前点数jk尚未超过击杀所需点数// 则其概率由dp[i-1][j]六等分后转移得到else {dp[i][j k] 1.0 / 6.0 * dp[i - 1][j];}}}}// 输出最后一行的最后一个元素// 表示打出第n个幸运币后造成伤害大于等于h-z点的概率System.out.println(String.format(%.5f, dp[y][h - z]));}}
}C
#include iostream
#include vector
#include iomanipusing namespace std;int main() {int y 0; // 掷出幸运币的总个数int z 0; // 全部造成的固定伤害int x_temp 0; // 时来运转获得的幸运币int n, h;cin n h;for (int i 0; i n; i) {int t, x;cin t x;// 时来运转if (t 1) {x_temp x;}// 幸运一掷else {y x_temp;x_temp 0;z x;}}// 如果固定伤害已经大于h直接输出1if (h - z 0) {cout fixed setprecision(10) 1 endl;}// 否则才需要进行dp过程else {// 初始化dp数组// dp[i][j]表示掷出了i个幸运币时// 有多大的概率可以取得和为j的结果即造成和为j的伤害。vectorvectordouble dp(y 1, vectordouble(h - z 1, 0));dp[0][0] 1.0;// 考虑每一个幸运币for (int i 1; i y; i) {// 对于每一个幸运币考虑打出i-1个硬币后的// 每一种求和结果的概率// 注意由于已经掷出了i-1个幸运币// 那么求和结果至少为i-1因为每个幸运币点数至少为1点// 因此j遍历时起点可以从i-1开始for (int j i - 1; j h - z; j) {// 如果求和j尚未在上一次投掷中取得// 则可以直接考虑下一个幸运币if (dp[i - 1][j] 0) {break;}// 遍历掷出六种不同点数k的情况// 当前点数则可以取得jkfor (int k 1; k 6; k) {// 如果当前点数jk超过了击杀所需点数// 则更新dp[i][h-z]// 为dp[i-1][j]对应的概率乘以(7-k)/6if (j k h - z) {dp[i][h - z] (7 - k) / 6.0 * dp[i - 1][j];break;}// 如果当前点数jk尚未超过击杀所需点数// 则其概率由dp[i-1][j]六等分后转移得到else {dp[i][j k] 1.0 / 6.0 * dp[i - 1][j];}}}}// 输出最后一行的最后一个元素// 表示打出第n个幸运币后造成伤害大于等于h-z点的概率cout fixed setprecision(5) dp[y][h - z] endl;}return 0;
}时空复杂度
时间复杂度O(yh)。其中y为投掷出的幸运币的总数h为BOSS总血量dp过程需要进行双重循环。
空间复杂度O(yh)。dp数组所占空间。如果使用滚动dp空间复杂度可以降低到O(h) 华为OD算法/大厂面试高频题算法练习冲刺训练 华为OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名目前已服务100同学成功上岸 课程讲师为全网50w粉丝编程博主吴师兄学算法 以及小红书头部编程博主闭着眼睛学数理化 每期人数维持在20人内保证能够最大限度地满足到每一个同学的需求达到和1v1同样的学习效果 60天陪伴式学习40直播课时300动画图解视频300LeetCode经典题200华为OD真题/大厂真题还有简历修改、模拟面试、专属HR对接将为你解锁 可上全网独家的欧弟OJ系统练习华子OD、大厂真题 可查看链接 OD算法冲刺训练课程表 OD真题汇总(持续更新) 绿色聊天软件戳 od1336了解更多
