一个人的巴黎

用户名：uq_36478041918

访问量：14995

签　名：

等　　级
排　　名	105
经　　验	8305
参赛次数	1
文章发表	70
年　　龄	0
在职情况	学生
学　　校	NTU
专　　业	计算机科学与技术

　　自我简介：

TA的其他文章

01背包问题(动态规划自下而上递推)
浏览：481

简单型背包(DFS深搜)
浏览：135

采药(dp动态规划之 01背包问题)
浏览：180

你可能喜欢

gets函数前有scanf读取时候，会读取缓存回车导致出错！！！

printf基础练习2 （C++代码）（受教了，，%#o和%#x的用途）三人行，必有我师，，多看题解会有收获

蓝桥杯2018年第九届真题-耐摔指数

　　作者: 一个人的巴黎　　　　发表时间：2022-04-05 00:47:50 浏览：346　|　评论：0　

原题链接：蓝桥杯2018年第九届真题-耐摔指数

```cpp
//打表发现后面可以利用前面——>动态规划
//由手机部数和层数两个变量决定测试次数结果——>动态规划

#include<iostream>
#include<cmath>

using namespace std;
const int N = 10000;
int f1[N + 1], f2[N + 1], f3[N + 3];//分别表示有1，2，3部手机
int n;
int main() {
	cin >> n;
	//只有一部手机的情况，只能从第一层开始扔，所以测试次数和层数相同
	for (int i = 1; i <= n; i++) {
		f1[i] = i;
	}
	//有两部手机，依此生成共i层的测试次数,从前往后递推生成
	for (int i = 1; i <= n; i++) {
		int ans = 0x3f3f3f;
		//第一部手机在第j层(1~i)扔下
		for (int j = 1; j <= i; j++) {
			//情况1：该手机完好，则还有两部手机，剩余i-j层需要测试(因为是递推上来的，前面层数肯定有结果了，所以只要看后面的)
			//情况2：该手机坏了，则还有一部手机，剩余j-1层需要测试(这一层坏了，那么就去测试下一层)
			int _max = 1 + max(f2[i - j], f1[j - 1]);//取max就是运气最坏，1是该次测试次数
			ans = min(_max, ans);//取min就是最佳策略
		}
		f2[i] = ans;
	}
	//有三部手机，依此生成共i层的测试次数,从前往后递推生成
	for (int i = 1; i <= n; i++) {
		int ans = 0x3f3f3f;
		//第一部手机在第j层(1~i)扔下
		for (int j = 1; j <= i; j++) {
			//情况1：该手机完好，则还有三部手机，剩余i-j层需要测试(因为是递推上来的，前面层数肯定有结果了，所以只要看后面的)
			//情况2：该手机坏了，则还有两部手机，剩余j-1层需要测试(这一层坏了，那么就去测试下一层)
			int _max = 1 + max(f3[i - j], f2[j - 1]);//取max就是运气最坏，1是该次测试次数
			ans = min(_max, ans);//取min就是最佳策略
		}
		f3[i] = ans;
	}
	cout << f3[n] << endl;
	return 0;
}
```

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

一个人的巴黎

TA的其他文章

你可能喜欢

用筛法求之N内的素数。（C语言代码）

C语言程序设计教程（第三版）课后习题7.1 （C++代码）

gets函数前有scanf读取时候，会读取缓存回车导致出错！！！

C语言程序设计教程（第三版）课后习题8.9 （C++代码）

printf基础练习2 （C++代码）（受教了，，%#o和%#x的用途）三人行，必有我师，，多看题解会有收获

蓝桥杯2018年第九届真题-耐摔指数

评论区

精彩推荐

2005年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言训练-邮票组合问题* （C语言代码）......

C二级辅导-等差数列（C语言代码）

C语言训练-立方和不等式（C语言代码）

c primer plus 第十二章 12.1小节

ASCII帮了大忙

C语言程序设计教程（第三版）课后习题8.1 （C语言代码）

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

1908题解

关于float，double变量的几点说明

一个人的巴黎

TA的其他文章

你可能喜欢

用筛法求之N内的素数。 （C语言代码）

C语言程序设计教程（第三版）课后习题7.1 （C++代码）

gets函数前有scanf读取时候，会读取缓存回车导致出错！！！

C语言程序设计教程（第三版）课后习题8.9 （C++代码）

printf基础练习2 （C++代码）（受教了，，%#o和%#x的用途）三人行，必有我师，，多看题解会有收获

蓝桥杯2018年第九届真题-耐摔指数

评论区

精彩推荐

2005年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言训练-邮票组合问题* （C语言代码）......

C二级辅导-等差数列 （C语言代码）

C语言训练-立方和不等式 （C语言代码）

c primer plus 第十二章 12.1小节

ASCII帮了大忙

C语言程序设计教程（第三版）课后习题8.1 （C语言代码）

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

1908题解

关于float，double变量的几点说明

用筛法求之N内的素数。（C语言代码）

　　评论区

C二级辅导-等差数列（C语言代码）

C语言训练-立方和不等式（C语言代码）