2018年蓝桥杯C/C++ B组省赛试题D：测试次数题解

ゞ浴缸里的玫瑰 2022-12-28 14:17 155阅读 0赞

### 文章目录 ###

*  题目描述
 *  输出
 *  解题思路
 *  解题代码

--------------------

# 题目描述 #

x星球的居民脾气不太好，但好在他们生气的时候唯一的异常举动是：摔手机。  
各大厂商也就纷纷推出各种耐摔型手机。x星球的质监局规定了手机必须经过耐摔测试，并且评定出一个耐摔指数来，之后才允许上市流通。

x星球有很多高耸入云的高塔，刚好可以用来做耐摔测试。  
塔的每一层高度都是一样的，与地球上稍有不同的是，他们的第一层不是地面，而是相当于我们的2楼。  
如果手机从第7层扔下去没摔坏，但第8层摔坏了，则手机耐摔指数=7。  
特别地，如果手机从第1层扔下去就坏了，则耐摔指数=0。  
如果到了塔的最高层第n层扔没摔坏，则耐摔指数=n  
为了减少测试次数，从每个厂家抽样3部手机参加测试。  
某次测试的塔高为1000层，如果我们总是采用最佳策略，在最坏的运气下最多需要测试多少次才能确定手机的耐摔指数呢？

# 输出 #

输出一个整数表示答案

# 解题思路 #

刚拿到题目时，我以为这道题目用二分来写，但是需要考虑到`二分适用于有无数台手机给我们去尝试`，而这道题目的手机数量是有限的。

**这是一道典型的dp问题。**

众所周知dp问题的关键在于填表，我们认为`dp[i][j]`表示 i 为使用到了几个手机，j 表示验证了几层，那么`dp[i][j]`的结果为测试了几次。

那么我们来考虑：

1、当只有一部手机时，**最坏情况下**我们需要从第 1 层一直测试到第 j 层楼，那么一共测试 j 次，`dp[1][j] = j`

2、当拥有两部或两部以上手机时，这时我们需要考虑**最优策略**。

当前我们在`第 k 层测试`，用到`第 i 部手机`时，测试会出现两种情况

![第k层示意图][k]

a.摔坏：如果在`第 k 层摔坏了`，那么我们只需要用剩下的 `i - 1 部手机`去测试剩下的`k - 1层楼`，即`dp[i - 1][k - 1]`

b.未摔坏：如果在`第 k 层没有摔坏`，那么我们只需要用 `i 部手机`去测试剩下的`n - k层楼`，即`dp[i][n - k]`

因为在这个测试过程中，我要**保证运气最坏**，因此`dp[i][k] = max(dp[i - 1][k - 1], dp[i][n - k]) + 1`

> 其中：
> 
> \+1 是指 无论当前这次测试摔坏、没摔坏，我都进行了一次测试
> 
> max 的目的 是要在测试过程中保证运气最坏，**即最坏情况**

*  状态转移方程：`dp[i][j] = min(d[i][j], max(dp[i - 1][k - 1], dp[i][n - k]) + 1)`
 *  其中min是时刻要**保证最优策略**

# 解题代码 #

//
    //  main.cpp
    //  2018lanqiao-d
    //
    //  Created by 陈洋 on 2020/10/11.
    //  Copyright © 2020 陈洋. All rights reserved.
    //
    
    #include <iostream>
    using namespace std;
    
    int dp[5][1010];
    int main(int argc, const char * argv[]) {
        
        int n = 3, m = 1000;
        
        for(int i = 1; i <= m; i++)
            dp[1][i] = i;   //当只有一个手机，就从1楼试到m楼，最坏情况是m
        
        for(int i = 2; i <= n; i++){
            //从两部手机开始循环，第i部手机
            for(int j = 1; j <= m; j++){
            //j表示有j层楼
                dp[i][j] = dp[i][j - 1] + 1;    //最坏情况下每一层楼都试一次
                for(int k = 2; k < j; k++){
        
                    /*
                     dp[i][j - k]代表当前这个手机在第k层没有摔坏，那么就看剩下的j - k层楼
                     dp[i - 1][k - 1]代表当前这个手机在第k层摔坏了，那么就看i - 1个手机在 k - 1层测试。
                     因为我用手机测试第k层时，如果摔坏了就说明在向下的k - 1层，如果没有摔坏则说明在向上的j - k层
                     不管测试结果如何，最后都摔了一次，则尾部 +1
                     */
                    int temp = max(dp[i][j - k], dp[i - 1][k - 1]) + 1;
                    dp[i][j] = min(dp[i][j] , temp);    //找到最优的k
                }
            }
        }
        
        cout << dp[3][1000] << endl;
        
        return 0;
    }

参考：[2018蓝桥杯B组第4题：测试次数][2018_B_4]

[k]: /images/20221120/c051403dc208491899efc3ad7254f6d5.png
[2018_B_4]: http://www.manongjc.com/detail/18-qmghnotunghkkhc.html