蓝桥杯备战 每日一题 （3）

?题目地址

所属于类型：动态规划

如何分析这个问题呢，咋一看如果采用二分的话，由于只给了三个测试样品，这样会导致三个测试样品根本不够用，那么应该怎么操作呢？

其实主要的思想：最佳策略还是二分得去寻找，不过要动态规划地去记录每次的结果，这里用两个数组去记录，一个记录两台手机测试 i 次能测试的高度，一个记录三台手机测量 i 次所能测试的高度，且注意题目说的是采取最佳策略，最坏情况下所要的测量次数

那么对于两台手机测试 i 次能测试的高度，一个测试高度包括什么，包括如果每次在 m = n /2 处测试的时候，用一部手机用 i -1 次可以测试完剩下的手机，如果是第一次摔坏了，还能测试 i - 1 ，加上第一次测试的，就测试了 i 层，如果没摔坏，那么可以视作用 两台手机测 i -1 次，即 a[i-1] 层

看看代码

#include<bits/stdc++.h>
using namespace std;
int a[105], b[105];
// 这两个数组的作用，a的数组用来记录只有测试手机为两台的情况
// b的数组来记录测试手机为 3 台的情况

// 这个算法自底向上
int main()
{
	int n, i = 0;  // i 用来记录测试次数
	cin >> n; // 输入 n
	// while 循环退出的条件就是如果 测试 i 次所能达到的层数
	// >= 所要测试的层数 n 的时候退出
	while (b[i]<n) {
		i++;    // 循环一次，代表测试次数加一
		a[i] = a[i - 1] + i;    //两部手机测量 i 次的情况

		b[i] = b[i - 1] + a[i - 1] + 1;   // 三台手机测量 i 次的情况

	}
	return 0;
}