题面
X 星球的居民脾气不太好，但好在他们生气的时候唯一的异常举动是：摔手机。
各大厂商也就纷纷推出各种耐摔型手机。x星球的质监局规定了手机必须经过耐摔测试，并且评定出一个耐摔指数来，之后才允许上市流通。
X 星球有很多高耸入云的高塔，刚好可以用来做耐摔测试。塔的每一层高度都是一样的，与地球上稍有不同的是，他们的第一层不是地面，而是相当于我们的 2 楼。
如果手机从第 7 层扔下去没摔坏，但第 8 层摔坏了，则手机耐摔指 = 7。 特别地，如果手机从第 1 层扔下去就坏了，则耐摔指数 = 0。 如果到了塔的最高层第 n 层扔没摔坏，则耐摔指数 = n。
为了减少测试次数，从每个厂家抽样 3 部手机参加测试。
某次测试的塔高为 1000 层，如果我们总是采用最佳策略，在最坏的运气下最多需要测试多少次才能确定手机的耐摔指数呢？
请填写这个最多测试次数。
题解
动态规划
记 f[i][j] 表示 i 部手机 j 层楼最优策略下所需的最大测试次数。
首先，对于最坏的情况，肯定是有多少层楼，就使用一部手机从第一层往上一层一层的扔多少次，直到其摔坏，其测试次数最坏情况即等于其层数，即初始化 f[i][j] = j。
对于只有一部手机 j 层楼的情况 f[1][j] = j 即为答案。而对于多部手机，我们可以不必一层一层从下往上进行测试，而可以多层多层的往上进行测试，而这个多层（记为 k）具体是多少我们不知道，则可以使用 枚举 的办法去求一个最优的 k 层进行测试。
则对于 f[i][j] （），我们从 k () 层摔下，如果摔坏了，证明其测试次数小于 k，在下面的 [1, k - 1] 层范围能够检测出来，则我们需在剩下的 i - 1 部手机 k - 1 层楼中检测出结果，而这正对应 f[i-1][k-1] 这个状态；反之，若在 k 层没有摔坏，则在 [k + 1, j] 层范围内能得出结果，及还需要在 i 部手机 j - k 层楼的情况下得出测试次数，也正好对应状态 f[i][j-k]。则结合上面两种在 k 摔下手机的情况， 使用 i 部手机 j 层楼的情况的最大测试次数等于下式子：
上式取两种情况下的最大测试次数的最大值且因为在 k 层进行了这次测试需 + 1，而这仅仅是在 k 层取到的，当 k 取不同值的时候，可能会存在更优的结果，所以需要遍历这个 k ，使得 f[i][j] 最小，才满足题意的最佳策略。
分析完毕！具体见代码。
答案：
19
代码
#include<bits/stdc++.h>
using namespace std;
int f[4][1005];
int main() {
int n = 1000;
for (int i = 1; i <= 3; i++) {
for (int j = 1; j <= n; j++) f[i][j] = j;
}
for (int i = 2; i <= 3; i++) {
for (int j = 1; j <= n; j++) {
for (int k = 1; k < j; k++) {
f[i][j] = min(f[i][j], max(f[i - 1][k - 1], f[i][j - k]) + 1);
}
}
}
cout << f[3][1000] << endl;
return 0;
}
| 标题： | 2018年第九届蓝桥杯省赛-D.测试次数 |
|---|---|
| 链接： | https://www.fightingok.cn/detail/205 |
| 更新： | 2022-09-18 22:48:02 |
| 版权： | 本文采用 CC BY-NC-SA 3.0 CN 协议进行许可 |