入门级动态规划:2018年第九届蓝桥杯省赛B组第四题—测试次数( 摔手机 )_从n层楼扔手机问题-程序员宅基地

技术标签: 蓝桥杯  DP  

目录

 

——下面列出用动态规划如何解决此问题——

①计算若干层楼用若干部手机最少需要摔多少次

②计算用若干部手机摔若干次最多可以确定多少层楼


原题描述:

        x星球的居民脾气不太好,但好在他们生气的时候唯一的异常举动是:摔手机。
各大厂商也就纷纷推出各种耐摔型手机。x星球的质监局规定了手机必须经过耐摔测试,并且评定出一个耐摔指数来,之后才允许上市流通。
        x星球有很多高耸入云的高塔,刚好可以用来做耐摔测试。塔的每一层高度都是一样的,与地球上稍有不同的是,他们的第一层不是地面,而是相当于我们的2楼。
        如果手机从第7层扔下去没摔坏,但第8层摔坏了,则手机耐摔指数=7。特别地,如果手机从第1层扔下去就坏了,则耐摔指数=0。如果到了塔的最高层第n层扔没摔坏,则耐摔指数=n

        为了减少测试次数,从每个厂家抽样3部手机参加测试。
        某次测试的塔高为1000层,如果我们总是采用最佳策略,在最坏的运气下最多需要测试多少次才能确定手机的耐摔指数呢?
        请填写这个最多测试次数。

        注意:需要填写的是一个整数,不要填写任何多余内容

        先把答案写在前面 19


当初没有注意到题目中的关键,只提供3部手机供你测试摔手机。直接一个二分法lg1000/lg2<10,交了个10,于是华丽丽的错掉了,二分法虽然可以在最短次数测到最坏可能性,但是致命的是它每次直接从中间高度摔手机,手机很有可能摔坏,如果想要用二分法摔出耐率指数是0的手机,那么足足需要摔坏10部手机!

还有要说明的是,假设手机个数是无限的可以采用二分法。

用二分法摔手机必须要确定耐摔指数 0~1000 ( 目标楼层数 ),因为耐率指数可以是0。当我们只有一层楼的时候,是需要摔一次才能确定耐摔指数是 0 还是 1 ,同理只有两层楼的时候需要摔两次才可以,并不是只需要1次( lg2 / lg2 = 1 ),因为排除了一个数后最后一个数也是需要摔的!

这个陷阱对于二分1000这个高度没什么,但如果是512层,二分法摔手机就得是10次了( lg513/lg2 ),而不是9次( lg512 / lg2 )。


        那如果只给了一部手机,怎么测出耐率指数呢?只好从1层开始摔,摔坏了就是(当前层数-1)的耐率指数。假如是两部手机呢?我一开始的想法是对1000进行分块,先用第一部手机摔出目标层数在哪一个小块里,然后再用第二部手机从那个小块最低层一层一层往上摔,直到确认为止。按照这个想法1000层需要分成 a*b*c 三个手机分别负责一个变量,最后就能确认目标层数。

        为了给自己的歪理加个公式增强点可信度,我想到了高中的基本不等式……3√(a*b*c)<=(a+b+c)/3 ,设a*b*c是1000,这么一算a+b+c最小值不就是30吗,a=b=c=10的时候成立。这么看来最难摔到的层数应该就是1000层了,第一部手机摔9次才能确定目标层数在901~1000( 摔101、201…901 ),然后再摔上9次才能确定目标层数在991~1000( 摔911、921…991 ),再摔上9次才能确定是1000( 摔992、993…1000 )确定出目标层数1000。可能有疑问为什么这里不考虑1了呢,因为我们采用的是自底向上排查,虽然1~10的范围必须要摔上10次才能确定每个值,但是1~10的范围只需要摔101和11就能确定下来( 两次 ),所以我们不考虑它会额外产生次数。因此这种方法摔手机27次能用三部手机摔出目标楼层!

        是不是有点太多了?!!

        ****显然是的,虽说分块分的很合理看上去无懈可击,但是这是建立在分同等长度块的前提下的。找到每个楼层的次数严重不均匀,因为是自底向上的摔,位于前面的楼层可以在短短几次就能确定范围,排在后面的楼层却需要许多次才能确定下范围,这无疑是不公平的,只有位于后面的楼层才会用最大次数摔后确定下来。

        那么为了均衡,把前面的块范围加大,后面块的范围缩小。这样前面的块很快能确定,但是它内部需要很多次才能确定到底是哪一个,而后面的块很多次才能确定但内部很小,因而很快可以确定是哪一个!完美的解决方法……

        如果是20层楼,我们用 2 部手机手机摔。那么最后一个确定的块范围定为1,那么5+5+4+3+2+1 这么划分是最合理的,在每一个块的最后一层扔第一部手机( 这是为了照顾第一层 ),确认下来目标楼层在哪个块之后在块内部用第二部手机扔。第一个块扔一次可以确定,但是内部需要4次;第二个块需要2次确定范围,内部需要4次确定;最后一个块需要摔上5次才能确定,但是内部摔上1次就可以。所以最后的结果应该是6次。这种分法恰好解决了必须要摔1楼的坑!最后一个块必摔一次,前面的块摔长度减一次。

        那当我们有三部手机呢,更深一层的分块,也就是说把全部楼层划分后用两部摔出每个块的内部……继续根据每个块的内部次数分配楼层!!这么来手算就太费劲了,现在看来显然是个动态规划问题了,分解成用 cnt 部手机可以在 ind 楼层最少摔多少次可以确定全部楼层?在一部手机的时候肯定是从1~1000了,一层一层确认。

以上内容分析了是如何得到最小摔手机次数的,核心在于大于两部手机时需要分块后摔第2~n部手机,且块内层数必须大于等于1,这样最后一部手机才有利用价值。


——下面列出用动态规划如何解决此问题——


①计算若干层楼用若干部手机最少需要摔多少次

1.设ind为当前层数,cnt为当前拥有手机个数,dp[ind][cnt]为此时最少摔多少次。

2.cnt=1时,没有任何花里胡哨,从低往高一层一层摔。

dp[ind][1]=ind

3.cnt>=2时

先看一个小例子,ind=4,cnt=2时,如何计算?目标当然是得到dp[4][2]的值。

—>用表格列出得到过程,cnt=1的情况先写出。

 

ind=1

ind=2

ind=3

ind=4

cnt=1

1

2

3

4

cnt=2

 

 

 

 

 

 

 

 

ind=1,cnt=2时,dp[1][2]显然也是1,一层楼摔一次足矣。

ind=2,cnt=2时,2层楼,摔一次肯定不够,必须摔两次。

 

ind=1

ind=2

ind=3

ind=4

cnt=1

1

2

3

4

cnt=2

1

2

 

 

 

 

 

 

ind=3的时候呢??

首先可以确定的是,用2层楼确定的最小次数+1,多摔上一次肯定能确定出3层楼最少用多少次。也就是说dp[3][2]最大值就是dp[2][2]+1  ,只需要确定的能不能等于dp[2][2]……

****有三层楼,手中拿出一部手机,可以去1~3层摔对不对,一开始说了那么多怎么个分块法得到最小次数, cnt 又大于1,肯定是需要分块后摔手机的。分块最小是块中有一层,这样下一部手机才不会没有用处。

于是乎拿出一部手机摔的层数肯定是(1+1)~(3-1)层(2层)

在2层这部手机摔碎了,那么就需要用剩下的cnt-1部手机来确定1层(2-1层~1层,共一层)手机是否会摔碎;(dp[1][1]+1)

在2层这部手机没有摔碎,那么就需要用cnt部手机来确定3层(2+1层~最高层,共一层)手机是否会摔碎;(dp[1][2]+1)

+1的意义是在2层摔的这部手机,是摔了一次的。

摔碎和没摔碎这两种情况的最大值就是在当前楼层摔手机可以得到的最小摔手机次数。

现在我们看看分析得到的结果

(1)    dp[3][2]<=dp[2][2]+1

(2)    dp[3][2]>=Max( dp[3-k][2]+1 , dp[k-1][1]+1 )

k大于1,小于ind(此处k只能等于2)。

我们需要的当然是最小值,即==>     dp[3][2]=Max( dp[3-k][2]+1 , dp[k-1][1]+1  )    =  2

 

ind=1

ind=2

ind=3

ind=4

cnt=1

1

2

3

4

cnt=2

1

2

2

 

 

 

 

 

同理分析ind=4,cnt=2时。

最大值:dp[3][2]+1 = 3

最小值: k=2,Max( dp[2][2]+1 ,dp[1][1]+1 ) = 3

               k=3,Max( dp[1][2]+1 ,dp[2][1]+1 )  = 3

dp[4][2] = 3

 

ind=1

ind=2

ind=3

ind=4

cnt=1

1

2

3

4

cnt=2

1

2

2

3

 

 

 

 

完成!四层楼用两部手机至少需要摔 dp[4][2] = 3 次。

总结以上,dp[ind][cnt]=Min( dp[k-1][cnt-1] ,dp[ind-k][cnt] ) +1     1 < k < ind

还有个毛病是:ind=1、2的时候,k是不存在的,这时候采用最大值 dp[ind-1][cnt]+1 即可,初始化 dp[0][cnt]=0

综合起来采用:dp[ind][cnt] = Min( 1+dp[ind-1][cnt] , 1+Max( dp[k-1][cnt-1] , dp[ind-k][cnt] )     1 < k < ind

#include<stdio.h>
#define Max(a,b) (a>b?a:b)
#define Min(a,b) (a<b?a:b)
int dp[1005][50];
int main(int argc, char* argv[])
{
    int n,m;
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
        dp[i][1]=i;
    for (int cnt=2;cnt<=m;cnt++)
    {
        for (int ind=1;ind<=n;ind++)
        {
            dp[ind][cnt]=1+dp[ind-1][cnt];
            for (int k=2;k<ind;k++)
                dp[ind][cnt]=Min(dp[ind][cnt],1+Max(dp[k-1][cnt-1],dp[ind-k][cnt]));
        }
    }
    printf("%d\n",dp[n][m]);
    return 0;
}

②计算用若干部手机摔若干次最多可以确定多少层楼

顺着逐级分块摔每部手机的思路,得到了第一个较为直观的做法。这次反过来,在确定手机数和摔手机次数后,计算一下能确定出的最大楼层数,然后遍历目标手机数下达到目标楼层的最小摔手机次数是多少。

和第一种做法同样的思路,摔一部手机会让楼层分为两部分,下面的楼层需要手机数 - 1 后确定,上面的楼层部分手机数不变确定,我们不知道该在哪个楼层将当前楼层分为两部分,所以我们遍历 来确定。

上面那个思路是否可以考虑将:变量由手机数量和楼层数改为手机数量和摔手机次数,最小摔手机次数这个因变量改为可确定楼层最大值呢?

这次已知摔手机次数 i 和手机数量 jdp[ i ][ j ] 为其可确定楼层最大值。当前可确定的最多楼层数就会是摔手机次数 i - 1 ,手机数量 jj - 1 下的可确定楼层数最大值之和,也不要忘了每次摔手机都会确定所摔楼层,每摔一部至少可以确定一层,所以推出:

dp[ i ][ j ] = dp[ i - 1 ][ j ] + dp[ i - 1 ][ j - 1 ] + 1

确定目标楼层 n 最多需要摔多少次手机呢?那肯定是手机只有一部的时候,最多需要 n 次才能确定目标楼层。我们设定摔手机次数 i 1n 遍历,计算当前次数下手机数为指定值 m 时的 dp[ i ][ m ] 是否大于等于目标楼层n,这样计算出最小的摔手机次数后输出即可。

这种做法显然是比做法①快不少的,减少了遍历寻找最佳分层点的部分,是更为优秀的~~

#include <stdio.h>
int dp[1005][50];
int main(int argc, char *argv[])
{
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
            dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1] + 1;
        if (dp[i][m] >= n)
        {
            printf("%d\n", i);
            break;
        }
    }
    return 0;
}

两种做法的C代码均给出 -> 输入 1000 3 即可得到结果 19

 

END

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/belous_zxy/article/details/80543276

智能推荐

apksigner完成apk的签名_apksigner 签名-程序员宅基地

文章浏览阅读2.3k次。有时候用第三方加固平台加固以后会让我们重新签名。还有就是上应用市场的时候,如果以前该应用已经在市场上上传过了,由于后面业务原因换了开发者账号再去上传就会提示我们去认领一个没有签名的包(unsign.apk),然后去签名上传进行MD5签名验证,如下图看到上面的提示不要慌,不就是加个签名么,apksigner就是SDK自带的签名工具,处于F:\android-sdk\build-tools\xxx目录下将上面的路径配置到系统环境变量path中,打开cmd,切换到unsign.apk目录下,建议.._apksigner 签名

java内省机制及PropertyUtils使用方法_propertyutils.snaketoline(field.getname());-程序员宅基地

文章浏览阅读1.3k次。背景 一般情况下,在Java中你可以通过get方法轻松获取beans中的属性值。但是,当你事先不知道beans的类型或者将要访问或修改的属性名时,该怎么办?Java语言中提供了一些像java.beans.Introspector这样类,实现了在运行时检测Java类并确定属性get和set方法的名称,结合Java中的反射机制就可以调用这些方法了。然而,这些APIs使用起来比较_propertyutils.snaketoline(field.getname());

LeetCode 516. Longest Palindromic Subsequence--最长回文子序列长度_leetcode longestpalindromesubseq连续字符不想等,长度为偶的回文子序列-程序员宅基地

文章浏览阅读536次。Given a string s, find the longest palindromic subsequence's length in s. You may assume that the maximum length of s is 1000.Example 1:Input:"bbbab"Output:4One possible longest palind_leetcode longestpalindromesubseq连续字符不想等,长度为偶的回文子序列长度

Android自定义View之自定义加载进度条(二)-程序员宅基地

文章浏览阅读189次。本文首发于公众号“AntDream”,欢迎微信搜索“AntDream”或扫描文章底部二维码关注,和我一起每天进步一点点自定义加载进度条Android自定义View之手把手带你自定义一个进度条上次我们已经把实线和虚线都绘制好了,这次我们就主要来解决更新的问题:怎么随着时间的推移逐渐地绘制进度条怎么在绘制的过程中加速进度条的绘制首先我们来解决第一个问题,也就是随着时间更新我们的..._setvalueinterpolator

c#判断字符串是否json-程序员宅基地

文章浏览阅读5.7k次。来源:https://www.cnblogs.com/cyq1162/p/3841766.html下载地址:  https://github.com/cyq1162/cyqdata/blob/master/Tool/JsonSplit.cs  https://github.com/cyq1162/cyqdata  using System;using System.C..._c#判断是json还是xml

python读取eml文件并用正则匹配邮箱_python 如何查看eml文件-程序员宅基地

文章浏览阅读992次。python读取eml文件并用正则匹配邮箱_python 如何查看eml文件

随便推点

Jquery插件之DataTables初探_jquery datatables 英文-程序员宅基地

文章浏览阅读2.5k次。今天闲来无事,就研究了一下Jquery的DataTables插件。感觉效果不错,支持排序和内容过滤(查询),在这里向大家推荐一下^_^不得不说之前犯了一个错误,这个插件应该叫做DataTable,而我把它当成了tablesort,实在不好意思。。。。。可以直接到官网上去下载下来,单击http://www.datatables.net/到官网上看看,什么API、demo之类的_jquery datatables 英文

算法:逆序对-程序员宅基地

文章浏览阅读8.5k次,点赞8次,收藏11次。逆序对什么是逆序对呢?百度百科这样解释:设 A 为一个有 n 个数字的有序集 (n>1),其中所有数字各不相同。如果存在正整数 i, j 使得 1 ≤ i < j ≤ n 而且 A[i] > A[j],则 <A[i], A[j]> 这个有序对称为 A 的一个逆序对,也称作逆序数。定义:对于一个包含N个非负整数的数组A[1…n],如果有i < j,且A[ i ]>A[ j ],则称(A[ i] ,A[ j] )为数组A中的一个逆序对。例如,数组(3_逆序对

SLAM导航机器人零基础实战系列:(四)差分底盘设计——3.底盘通信协议_slam 实战-程序员宅基地

文章浏览阅读1.2k次。SLAM+语音机器人DIY系列:(四)差分底盘设计——3.底盘通信协议摘要 运动底盘是移动机器人的重要组成部分,不像激光雷达、IMU、麦克风、音响、摄像头这些通用部件可以直接买到,很难买到通用的底盘。一方面是因为底盘的尺寸结构和参数是要与具体机器人匹配的;另一方面是因为底盘包含软硬件整套解决方案,是很多机..._slam 实战

LOJ #6010. 「网络流 24 题」数字梯形-程序员宅基地

文章浏览阅读89次。#6010. 「网络流 24 题」数字梯形题目描述给定一个由n nn行数字组成的数字梯形如下图所示。梯形的第一行有m mm个数字。从梯形的顶部的m mm个数字开始,在每个数字处可以沿左下或右下方向移动,形成一条从梯形的顶至底的路径。分别遵守以下规则:从梯形的顶至底的m mm条路径互不相交;从梯形的顶至底的m mm..._7-60 数字梯形 (110 分) 给定一个由n行数字组成的数字梯形如下图所示。梯形的第一

Ubuntu20.04 + RTX 3090(兼容RTX 2080 Ti) + Pytorch1.7配置方法_2080ti ubuntr20.04-程序员宅基地

文章浏览阅读2.2k次。背景介绍:由于在Ubuntu16.04系统上安装RTX 3090显卡驱动有点吃力(各种Error和不兼容),使用最新Ubuntu20.04系统搭配最新的RTX 3090显卡配置最新的Pytorch【(*^▽^*)】前期准备: 1、Ubuntu20.04下载:Ubuntu20.4_amd64_desktop.iso 2、UNtebootin光盘刻录软件下载:unetbootin,选择Windows下载 3、NVID..._2080ti ubuntr20.04

Struts + Spring +ibatis 整合开发步骤_struts+spring+ibatis-程序员宅基地

文章浏览阅读329次。一.添加Spring 、Struts框架对web.xml文件的修改1. 添加Spring框架2. 在web.xml中引入Spring配置文件(注意:applicationContext.xml文件的路径)context-param> param-name>contextConfigLocationparam-name> param-v_struts+spring+ibatis