蓝桥杯每日一题2023.10.26

朱雀 2024-02-20 08:46 91阅读 0赞

[测试次数 - 蓝桥云课 (lanqiao.cn)][- _ _lanqiao.cn]

### 题目描述 ###

![9b2d1cb137c74854a37e72f0837d5ea4.png][]

### 题目分析 ###

对于本题我们可以使用动态规划来分析

**dp\[i\]\[j\]代表剩余i层，j台手机的情况下对应的测试数量**

分类进行讨论一下：

1.当只剩下一台手机的时候，只能从第一层一层一层往上尝试，尝试到第几层摔坏就是几

2.当j = 2，假设剩余k层，总层数为n,dp\[k\]\[2\]可以分为以下两种情况：

①摔坏 dp\[k\]\[2\] = dp\[k - 1\]\[1\];

②没摔坏 dp\[k\]\[2\] = dp\[n - k\]\[2\] //n - k相当于把下面的k层全部砍掉

当j = 3同理

由于考虑的是最坏的情况，所以我们需要在手机摔坏和没摔坏这两种情况中取到最大的测试次数，由于我们要考虑最坏的最优情况，所以我们要在每层最大的里面选择最小的

#include<bits/stdc++.h>
    using namespace std;
    const int N = 2e3 + 10;
    int dp[N][N];
    int main()
    {
    	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    	int l = 1, r = 1000;
    	for(int i = 1; i <= 1000; i ++)dp[i][1] = i;//第一部手机 
    	for(int j = 2; j <= 3; j ++)//第二和第三部手机 
    	{
    		for(int i = 1; i <= 1000; i ++)
    		{
    			dp[i][j] = 1e9 + 10;
    			for(int k = 1; k <= i; k ++)//手机在第k层是否摔坏 
    			{
    				dp[i][j] = min(max(dp[k - 1][j - 1], dp[i - k][j]) + 1, dp[i][j]); 
    			}
    		}
    	}
    	cout << dp[1000][3];
    	return 0;
    }

[- _ _lanqiao.cn]: https://www.lanqiao.cn/problems/616/learning/?first_category_id=1&page=1&sort=students_count&second_category_id=3&name=%E6%B5%8B%E8%AF%95%E6%AC%A1%E6%95%B0
[9b2d1cb137c74854a37e72f0837d5ea4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/45de8a7d8b5f4b4a8586460041bcea2d.png

发表评论取消回复

表情：

评论列表（有 0 条评论，91人围观）

还没有评论，来说两句吧...

相关阅读

相关日志统计(蓝桥杯每日一题)

日志统计(蓝桥杯每日一题) 小明维护着一个程序员论坛。现在他收集了一份”点赞”日志，日志共有 N 行。其中每一行的格式是： ts id 表示在 ts 时

柔情只为你懂/ 2024年03月26日 13:13/ 0 赞/ 90 阅读

相关截断数组（蓝桥杯每日一题）

截断数组（蓝桥杯每日一题）给定一个长度为 n的数组 a1,a2,…,an。现在，要将该数组从中间截断，得到三个非空子数组。要求，三个子数组内各元素之和都相等。

淡淡的烟草味﹌/ 2024年03月26日 12:32/ 0 赞/ 54 阅读

相关蓝桥杯每日一题2023.9.10

[蓝桥杯2023年第十四届省赛真题-接龙数列 - C语言网 (dotcpp.com)][2023_-_ - C_ _dotcpp.com] 题目描述对于一个长度为 K

桃扇骨/ 2024年03月04日 08:03/ 0 赞/ 78 阅读

相关蓝桥杯每日一题2023.9.8

[蓝桥杯2023年第十四届省赛真题-飞机降落 - C语言网 (dotcpp.com)][2023_-_ - C_ _dotcpp.com] 题目描述 N 架飞机准备降落

r囧r小猫/ 2024年03月04日 07:39/ 0 赞/ 90 阅读

相关蓝桥杯每日一题2023.10.17

[迷宫 - 蓝桥云课 (lanqiao.cn)][- _ _lanqiao.cn] 题目描述 ![f123b4885ad441029120fa79c0a4a1d0.pn

布满荆棘的人生/ 2024年03月02日 10:54/ 0 赞/ 85 阅读

相关蓝桥杯每日一题2023.9.19

[蓝桥杯2021年第十二届省赛真题-砝码称重 - C语言网 (dotcpp.com)][2021_-_ - C_ _dotcpp.com] 题目描述你有一架天平和 N

╰半橙微兮°/ 2024年03月02日 04:12/ 0 赞/ 25 阅读

相关蓝桥杯每日一题2023.10.26

[测试次数 - 蓝桥云课 (lanqiao.cn)][- _ _lanqiao.cn] 题目描述 ![9b2d1cb137c74854a37e72f0837d5ea4.

朱雀/ 2024年02月20日 08:46/ 0 赞/ 92 阅读

相关蓝桥杯每日一题2023.11.11

题目描述 [“蓝桥杯”练习系统 (lanqiao.cn)][_lanqiao.cn] ![4ef899a93197493aa5c46db23ed79c0f.png][]

朱雀/ 2024年02月18日 09:02/ 0 赞/ 94 阅读

相关蓝桥杯每日一题2023.11.24

题目描述 ![74f53029c5b2425ebba5149b74392ac4.png][] include <stdio.h> define N 10

桃扇骨/ 2024年02月17日 09:57/ 0 赞/ 41 阅读

相关蓝桥杯每日一题2023.11.22

题目描述 ![9fe1856dc34b47d7933b1e56fda879be.png][] 题目分析由题目知其每个品牌积分一定小于315故直接暴力枚举每个品牌

妖狐艹你老母/ 2024年02月17日 09:08/ 0 赞/ 41 阅读