网站编辑的栏目怎么做,中国现代公路建设有限公司网站,做英语教具的网站,成都网站备案太慢原题描述#xff1a; x星球的居民脾气不太好#xff0c;但好在他们生气的时候唯一的异常举动是#xff1a;摔手机。 各大厂商也就纷纷推出各种耐摔型手机。x星球的质监局规定了手机必须经过耐摔测试#xff0c;并且评定出一个耐摔指数来#xff0c;之后才允许上市流通。 …原题描述 x星球的居民脾气不太好但好在他们生气的时候唯一的异常举动是摔手机。 各大厂商也就纷纷推出各种耐摔型手机。x星球的质监局规定了手机必须经过耐摔测试并且评定出一个耐摔指数来之后才允许上市流通。 x星球有很多高耸入云的高塔刚好可以用来做耐摔测试。塔的每一层高度都是一样的与地球上稍有不同的是他们的第一层不是地面而是相当于我们的2楼。 如果手机从第7层扔下去没摔坏但第8层摔坏了则手机耐摔指数7。
特别地如果手机从第1层扔下去就坏了则耐摔指数0。如果到了塔的最高层第n层扔没摔坏则耐摔指数n 为了减少测试次数从每个厂家抽样3部手机参加测试。 某次测试的塔高为1000层如果我们总是采用最佳策略在最坏的运气下最多需要测试多少次才能确定手机的耐摔指数呢 请填写这个最多测试次数。 注意需要填写的是一个整数不要填写任何多余内容
答案19 文章目的 读完题后我们追求的不是要写出得数至少对于本博客是不够的而是用代码实现方法并思考是否可以优化。
其实本题的方法是非常多种多样的。非常适合锻炼思维。
我们把问题扩展到n个手机来思考。
手机k个楼n层最终结果M次。
时空复杂度目录
暴力 O(N!)
DP: O(N*N*K) O(N*K)
压空间 O(N*N*K) O(N)
四边形不等式优化 O(N*N)
换思路 O(K*M)
最优 O(K*M) O(N)
文末有测试大家可以去直观感受一下各方法运行的效率
二分 容易想到二分思路不断二分范围取中点测验是否会摔坏然后缩小一半范围继续尝试很显然答案为logN2为底
但是二分得出的答案是不对的。注意:我们要保证在都手机摔完之前能确定耐摔指数到底是多少。
举例
我们在500楼摔坏了在250楼摔又坏了。接下来我们只能从1楼开始一层一层试
因为如果我们在125层摔坏了就没有手机可以用也就是永远都测不出来而这是不被允许的。其实我们连测第2层都不敢测因为在第2层摔坏了我们就无法知道手机在第一层能否被摔坏。所以只有一部手机时我们只敢从第一层开始摔。 尝试较优的策略 既然二分是不对的我们继续分析摔手机的最优策略到底是如何的。
只有一部手机时我们只敢从第一层开始摔。
有两部手机的时候我们就敢隔层摔了因为一部手机坏了我们还有另一部来继续试。
这时就有点意思了我们分析情况
情况1假设我们第一部手机在i层摔坏了然后最坏情况还要试多少次这时我们还剩一部手机所以只敢一层一层试最坏情况要试到i-1层共试了i次。
情况2假设我们第一部手机在i层试了但是没摔坏然后最坏情况还要试多少次这时发现算情况2时依旧是相似的问题确定了可以用递归来解。 最优解最小值是决策后两种情况的最差情况最大值我们的本能感觉应该就是让最差情况好一点让最好情况差一点这样比较接近正确答案。比如两部手机一百层我们可以在50层摔没坏这一次就很赚我们没摔坏手机还把范围缩小了50层。如果坏了就比较坑了我们要从1试到50。虽然可能缩小一半但是最坏情况次数太多所以肯定要从某个低于五十的层开始尝试。
以上几行是为了让读者理解决策下面正文分析 归纳表达式 假设我们的楼一共n层我们的i可以取1-n任意值有很多种可能的决策我们的最小值设为fnkn代表楼高范围为1-100或101-200其实都一样k代表手机数.
我们假设的决策是在第i楼扔
对于情况一手机少了一部并且我们确定了范围一定在第i楼以下所以手机-1层数为i-1这时fnkf(i-1,k-1).1
对于情况二手机没少并且我们确定了范围一定在第i楼之上所以手机数不变而层数-i层这时fnkf(n-i,k).1
归纳出
fnkmin maxf(i-1,k-1) f(n-i,k) i取1-n任意数 1
简单总结怎么确定第一个手机在哪扔每层都试试哪层的最坏情况max最好min就去哪层扔。 写出暴力递归
按照分析出来的表达式我们可以写出暴力递归 public static int solution1(int nLevel, int kChess) {if (nLevel 0) {return 0;}//范围缩小至0if (kChess 1) {return nLevel;}//每层依次试int min Integer.MAX_VALUE;//取不影响结果的数for (int i 1; i ! nLevel 1; i) {//尝试所有决策取最优min Math.min(min,Math.max(Process1(i - 1, kChess - 1),Process1(nLevel - i, kChess)));}return min 1;//别忘了加上本次} 改为动态规划 具体思路如下
https://blog.csdn.net/hebtu666/article/details/79912328 public static int solution2(int nLevel, int kChess) {if (kChess 1) {return nLevel;}int[][] dp new int[nLevel 1][kChess 1];for (int i 1; i ! dp.length; i) {dp[i][1] i;}for (int i 1; i ! dp.length; i) {for (int j 2; j ! dp[0].length; j) {int min Integer.MAX_VALUE;for (int k 1; k ! i 1; k) {min Math.min(min,Math.max(dp[k - 1][j - 1], dp[i - k][j]));}dp[i][j] min 1;}}return dp[nLevel][kChess];} 压缩空间 我们发现对于状态转移方程只和上一盘排的dp表和左边的dp表有关所以我们不需要把值全部记录用两个长度为n的数组不断更新即可具体对dp压缩空间的思路也是很重要的我在其它文章中有提过在这里就不写了 public static int solution3(int nLevel, int kChess) {if (kChess 1) {return nLevel;}int[] preArr new int[nLevel 1];int[] curArr new int[nLevel 1];for (int i 1; i ! curArr.length; i) {curArr[i] i;}//初始化for (int i 1; i ! kChess; i) {//先交换int[] tmp preArr;preArr curArr;curArr tmp;//然后打新的一行for (int j 1; j ! curArr.length; j) {int min Integer.MAX_VALUE;for (int k 1; k ! j 1; k) {min Math.min(min, Math.max(preArr[k - 1], curArr[j - k]));}curArr[j] min 1;}}return curArr[curArr.length - 1];} 四边形不等式优化 四边形不等式是一种比较常见的优化动态规划的方法
定义如果对于任意的a1≤a2b1≤b2有m[a1,b1]m[a2,b2]≤m[a1,b2]m[a2,b1]那么m[i,j]满足四边形不等式。
对s[i,j-1]≤s[i,j]≤s[i1,j]的证明
设mk[i,j]m[i,k]m[k,j]s[i,j]d
对于任意kd有mk[i,j]≥md[i,j]这里以m[i,j]min{m[i,k]m[k,j]}为例,max的类似接下来只要证明mk[i1,j]≥md[i1,j]那么只有当s[i1,j]≥s[i,j]时才有可能有mk[i1,j]≥md[i1,j]
(mk[i1,j]-md[i1,j])-(mk[i,j]-md[i,j])
(mk[i1,j]md[i,j])-(md[i1,j]mk[i,j])
(m[i1,k]m[k,j]m[i,d]m[d,j])-(m[i1,d]m[d,j]m[i,k]m[k,j])
(m[i1,k]m[i,d])-(m[i1,d]m[i,k])
∵m满足四边形不等式∴对于ii1≤kd有m[i1,k]m[i,d]≥m[i1,d]m[i,k]
∴(mk[i1,j]-md[i1,j])≥(mk[i,j]-md[i,j])≥0
∴s[i,j]≤s[i1,j]同理可证s[i,j-1]≤s[i,j]
证毕 通俗来说
优化策略1我们在求k1手机n层楼时最后发现第一个手机在m层扔导致了最优解的产生。那我们在求k个手机n层楼时第一个手机的策略就不用尝试m层以上的楼了。
优化策略2我们在求k个手机n层楼时最后发现第一个手机在m层扔导致了最优解的产生。那我们在求k个手机n1层楼时就不用尝试m层以下的楼了。 public static int solution4(int nLevel, int kChess) {if (kChess 1) {return nLevel;}int[][] dp new int[nLevel 1][kChess 1];for (int i 1; i ! dp.length; i) {dp[i][1] i;}int[] cands new int[kChess 1];for (int i 1; i ! dp[0].length; i) {dp[1][i] 1;cands[i] 1;}for (int i 2; i nLevel 1; i) {for (int j kChess; j 1; j--) {int min Integer.MAX_VALUE;int minEnum cands[j];int maxEnum j kChess ? i / 2 1 : cands[j 1];//优化策略for (int k minEnum; k maxEnum 1; k) {int cur Math.max(dp[k - 1][j - 1], dp[i - k][j]);if (cur min) {min cur;cands[j] k;//最优解记录层数}}dp[i][j] min 1;}}return dp[nLevel][kChess];}
注对于四边形不等式的题目比赛时不需要严格证明
通常的做法是打表出来之后找规律然后大胆猜测显然可得。手动滑稽 换一种思路 有时最优解并不是优化来的。
当你对着某个题冥思苦想了好久无论如何也不知道怎么把时间优化到合理范围可能这个题的最优解就不是这种思路这时试着换一种思路思考可能会有奇效。
比如训练时一道贪心我死活往dp想肝了两个小时以后不主攻这个方向的队友三分钟就有贪心思路了泪目不要把简单问题复杂化 我们换一种思路想问题
原问题n层楼k个手机最多测试次数
反过来看问题k个手机扔m次最多能确定多少层楼
我们定义dp[i][j]i个手机扔j次能确定的楼数。
分析情况依旧是看第一部手机在哪层扔的决策同样我们的决策首先要保证能确定从1层某一段而不能出现次数用完了还没确定好的情况。以这个为前提保证了每次扔的楼层都是最优的就能求出结果。
依旧是取最坏情况min情况1情况2
情况1第一个手机碎了我们就需要用剩下的i-1个手机和j-1次测试次数往下去测dp[i-1][j-1]。那我们能确定的层数是无限的因为本层以上的无限层楼都不会被摔坏。dp[i-1][j-1]无穷无穷
情况2第一个手机没碎那我们就看i个手机扔j-1次能确定的楼数向上试当前楼高h
归纳表达式要取最差情况所以就是只有情况2dp[i][j]dp[i-1][j-1]h
那这个h到底是什么呢取决于我敢从哪层扔。因为次数减了一次我们还是要考虑i个球和j-1次的最坏情况能确定多少层我才敢在层数1的地方扔。这是重点
也就是dp[i][j-1]的向上一层hdp[i][j-1]1 总min情况1情况2min无穷dp[i-1][j-1]dp[i][j-1]1dp[i-1][j-1]dp[i][j-1]1
这是解决k个手机扔m次最多能确定多少层楼
原问题是n层楼k个手机最多测试次数。
所以我们在求的过程中何时能确定的层数大于n输出扔的次数即可 最优解
我们知道完全用二分扔需要logN1次这也绝对是手机足够情况下的最优解我们做的这么多努力都是因为手机不够摔啊。。。。所以当我们的手机足够用二分来摔时直接求出logN1即可。 当然我们求dp需要左边的值和左上的值 依旧可以压缩空间从左往右更新previous记录左上的值。
求自己时也要注意记录否则更新过后后面的要用没更新过的值左上方就找不到了。
记录之后求出当前数值把记录的temp值给了previous即可。 public static int solution5(int nLevel, int kChess) {int bsTimes log2N(nLevel) 1;if (kChess bsTimes) {return bsTimes;}int[] dp new int[kChess];int res 0;while (true) {res;//压缩空间记得记录次数int previous 0;for (int i 0; i dp.length; i) {int tmp dp[i];dp[i] dp[i] previous 1;previous tmp;if (dp[i] nLevel) {return res;}}}}public static int log2N(int n) {int res -1;while (n ! 0) {res;n 1;}return res;} 本题只是填空题第一种方法就完全能算出来就是为了追求最优解追求思维的锻炼。写下了本文。 测试
暴力 O(N!)
DP: O(N*N*K) O(N*K)
压空间 O(N*N*K) O(N)
四边形不等式优化 O(N*N)
最优 O(K*M) O(N) long start System.currentTimeMillis();solution1(30, 2);long end System.currentTimeMillis();System.out.println(cost time: (end - start) ms);start System.currentTimeMillis();solution2(30, 2);end System.currentTimeMillis();System.out.println(cost time: (end - start) ms);start System.currentTimeMillis();solution3(30, 2);end System.currentTimeMillis();System.out.println(cost time: (end - start) ms);start System.currentTimeMillis();solution4(30, 2);end System.currentTimeMillis();System.out.println(cost time: (end - start) ms);start System.currentTimeMillis();solution5(30, 2);end System.currentTimeMillis();System.out.println(cost time: (end - start) ms);
/*
结果
cost time: 7043 ms
cost time: 0 ms
cost time: 0 ms
cost time: 0 ms
cost time: 0 ms
*/
暴力时间实在是太久了只测一个302 后四种方法测的大一些差点把电脑测炸了cpu100内存100
solution(100000, 10):
solution2 cost time: 202525 ms solution3 cost time: 38131 ms solution4 cost time: 11295 ms solution5 cost time: 0 ms 感受最优解的强大
solution5(1000 000 000,100):0 ms
solution5(1000 000 000,10):0 ms
最优解永远都是0 ms我也是服了。。 对比方法在时间复杂度相同的条件下空间复杂度一样会影响时间因为空间太大的话申请空间是相当浪费时间的。并且空间太大电脑会炸所以不要认为空间不重要。
