[动态规划优化] 鸡蛋的硬度 状态重定义

2024-02-21 05:04

本文主要是介绍[动态规划优化] 鸡蛋的硬度 状态重定义,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目描述

有一个教授有一批一模一样的鹰蛋。有一天他来到了一栋楼的脚下,他突然想知道自己的鹰蛋从这栋楼的多少层扔下时恰好不碎。
一颗鹰蛋如果从i层摔下没有碎,那么从小于j层摔下也不会碎,如果从j层摔下碎了,从大于j层摔下也会摔碎。如果恰好存在一层n,从n层摔下鹰蛋未碎,而从n+1层摔下碎了,那么这批鹰蛋恰好从n层摔下未碎。如果从第一层摔下碎了,那么称恰好从0层摔下未碎;另一方面,如果从最高层(N层)摔下未碎,那么称恰好从N层摔下未碎
这个教授想知道从第多少层恰好摔下不碎,但是这个教授想使用最少的试验次数来得到这个值。
现已知鹰蛋的个数M和楼层高度N,试问在最坏情况下,这个教授最少需要试验多少次来得到他想要的结果?
比如:M为1,N为3。那么这个教授为了得到结果,就必须从一层一层测试,在最坏情况下,最少需要3次试验。但是如果M=2,N=3,那么他就可以第一次从二层扔下,不管碎了还是没碎,他都只需再扔一次即可得到结果,即需要做2次试验即可。

关于输入

有多组输入,每一组输入单独一行。
分别为两个如题所述的正整数N(大于0小于400001),M (大于0小于N+1)中间用空格隔开。
如果得到的N和M都为0,表示输入结束。

关于输出

每组输出单独一行,输出需要试验的次数K。

例子输入
100 1
100 2
0 0
例子输出
100
14
提示信息

动态规划,由于输入量比较大,最好尽量优化算法。

解题分析

首先介绍一种初级的方法,这种方法可以用来解决小数据的情况。我们定义一个dp数组,其中dp[i][j]表示用i个鸡蛋去测j层楼在最坏的情况下所需要测试的最少次数。

接下来,我们需要考虑如何去更新这个dp数组。首先,我们可以知道的是,如果我们手头只有一个鸡蛋,那么,在运气最差的情况下,我们不得不从第一层开始测,所以这个时候的最少次数就是楼层的层数。

如果我们只有一层楼,那么根据题意,无论我们这一下鸡蛋碎没碎,我们都可以定义这个鸡蛋的硬度了,所以这个时候我们的最少的次数就是1。

在其他情况,假定我们有m个鸡蛋需要测试n层楼,我们怎样可以得到运气最差的情况下测试所用的最少的次数呢?一个想法就是去枚举期我们所扔第一个鸡蛋的层数。我们可以假定我们第一个鸡蛋一开始从k层去扔,那么,如果碎了,我们的问题就变成是用m-1个鸡蛋测k-1层楼;如果没碎,我们的问题就变成是用m个鸡蛋去测n-k层楼。

代码实现1
#include <iostream>
using namespace std;int dp[200][200]={0};int f(int n,int m){if(dp[n][m]) return dp[n][m];if(m==1) return n;if(n==1) return 1;int res=1e9;for(int k=1;k<=n;k++){res=min(res,max(f(k-1,m-1)+1,f(n-k,m)+1));}return dp[n][m]=res;
}int main(){int n,m;while(cin>>n>>m){if(n==0 && m==0) return 0;cout<<f(n,m)<<endl;}return 0;
}

当然直接用for循环打表也可以:

#include <iostream>
using namespace std;int dp[100000][100]={0};int main(){int n,m;while(cin>>n>>m){if(n==0 && m==0) return 0;for(int i=1;i<=n;i++){dp[i][1]=i;}for(int i=1;i<=n;i++)for(int j=2;j<=m;j++){dp[i][j]=i;for(int k=1;k<=i;k++){dp[i][j]=min(dp[i][j],max(dp[k-1][j-1],dp[i-k][j])+1);}}cout<<dp[n][m]<<endl;}return 0;
}
解题分析2

当然,如果仅仅如此的话,还不能完美的解决本题,因为我们可以发现,N的值很大,而我们现在的这算法的时间复杂度是n^2*m,当N大于10000时,我们就会超时了。

如果去优化呢?这里需要采用状态重定义的技巧。我们发现,dp[n][m]表示m个鸡蛋测n层楼,当鸡蛋的数目一定时,我们增加楼层的数量,可以发现需要尝试的次数也会增加,也就是说,这两个量是成正比的关系,而从直观上理解,尝试的次数作为一个取min的量,其值肯定要比楼层数要小的多,所以我们可以重新定义一下dp数组的状态。

我们交换尝试的次数和楼层数的位置,dp[i][j]表示i个鸡蛋尝试j次可以到达的最大楼层数。这样,当我们发现dp[i][k-1]小于n时,说明k-1次不能测出鸡蛋的硬度,且我们发现dp[i][k]>=n,那么我们要求的次数就是k次。(相当于对我们之前那个过程的逆向处理)。

于是dp[i][j]=dp[i-1][j-1](有可能鸡蛋碎了,那就测下面的楼层)+dp[i][j-1](有可能鸡蛋没碎,那就测上面的楼层)+1(当前的这个楼层)。

 代码实现
#include <iostream>
#define Max_trial 100
#define MaxM 400005
using namespace std;int dp[MaxM][Max_trial]={0};int main(){int n,m;for(int i=0;i<Max_trial;i++){dp[1][i]=i;}for(int i=2;i<MaxM;i++)for(int j=1;j<Max_trial;j++){dp[i][j]=1+dp[i][j-1]+dp[i-1][j-1];}while(cin>>n>>m){if(n==0 && m==0) return 0;if(m==1) {cout<<n<<endl;continue;}for(int i=0;i<Max_trial;i++){if(dp[m][i]>=n){cout<<i<<endl;break;}}}return 0;
}

这篇关于[动态规划优化] 鸡蛋的硬度 状态重定义的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/730650

相关文章

SpringBoot中HTTP连接池的配置与优化

《SpringBoot中HTTP连接池的配置与优化》这篇文章主要为大家详细介绍了SpringBoot中HTTP连接池的配置与优化的相关知识,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一... 目录一、HTTP连接池的核心价值二、Spring Boot集成方案方案1:Apache HttpCl

PyTorch高级特性与性能优化方式

《PyTorch高级特性与性能优化方式》:本文主要介绍PyTorch高级特性与性能优化方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、自动化机制1.自动微分机制2.动态计算图二、性能优化1.内存管理2.GPU加速3.多GPU训练三、分布式训练1.分布式数据

Python Selenium动态渲染页面和抓取的使用指南

《PythonSelenium动态渲染页面和抓取的使用指南》在Web数据采集领域,动态渲染页面已成为现代网站的主流形式,本文将从技术原理,环境配置,核心功能系统讲解Selenium在Python动态... 目录一、Selenium技术架构解析二、环境搭建与基础配置1. 组件安装2. 驱动配置3. 基础操作模

MySQL中like模糊查询的优化方案

《MySQL中like模糊查询的优化方案》在MySQL中,like模糊查询是一种常用的查询方式,但在某些情况下可能会导致性能问题,本文将介绍八种优化MySQL中like模糊查询的方法,需要的朋友可以参... 目录1. 避免以通配符开头的查询2. 使用全文索引(Full-text Index)3. 使用前缀索

C#实现高性能Excel百万数据导出优化实战指南

《C#实现高性能Excel百万数据导出优化实战指南》在日常工作中,Excel数据导出是一个常见的需求,然而,当数据量较大时,性能和内存问题往往会成为限制导出效率的瓶颈,下面我们看看C#如何结合EPPl... 目录一、技术方案核心对比二、各方案选型建议三、性能对比数据四、核心代码实现1. MiniExcel

慢sql提前分析预警和动态sql替换-Mybatis-SQL

《慢sql提前分析预警和动态sql替换-Mybatis-SQL》为防止慢SQL问题而开发的MyBatis组件,该组件能够在开发、测试阶段自动分析SQL语句,并在出现慢SQL问题时通过Ducc配置实现动... 目录背景解决思路开源方案调研设计方案详细设计使用方法1、引入依赖jar包2、配置组件XML3、核心配

使用Python实现IP地址和端口状态检测与监控

《使用Python实现IP地址和端口状态检测与监控》在网络运维和服务器管理中,IP地址和端口的可用性监控是保障业务连续性的基础需求,本文将带你用Python从零打造一个高可用IP监控系统,感兴趣的小伙... 目录概述:为什么需要IP监控系统使用步骤说明1. 环境准备2. 系统部署3. 核心功能配置系统效果展

springboot使用Scheduling实现动态增删启停定时任务教程

《springboot使用Scheduling实现动态增删启停定时任务教程》:本文主要介绍springboot使用Scheduling实现动态增删启停定时任务教程,具有很好的参考价值,希望对大家有... 目录1、配置定时任务需要的线程池2、创建ScheduledFuture的包装类3、注册定时任务,增加、删

SpringBoot基于配置实现短信服务策略的动态切换

《SpringBoot基于配置实现短信服务策略的动态切换》这篇文章主要为大家详细介绍了SpringBoot在接入多个短信服务商(如阿里云、腾讯云、华为云)后,如何根据配置或环境切换使用不同的服务商,需... 目录目标功能示例配置(application.yml)配置类绑定短信发送策略接口示例:阿里云 & 腾

C 语言中enum枚举的定义和使用小结

《C语言中enum枚举的定义和使用小结》在C语言里,enum(枚举)是一种用户自定义的数据类型,它能够让你创建一组具名的整数常量,下面我会从定义、使用、特性等方面详细介绍enum,感兴趣的朋友一起看... 目录1、引言2、基本定义3、定义枚举变量4、自定义枚举常量的值5、枚举与switch语句结合使用6、枚