Lanqiao-2018-CB省赛 测试次数

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

x星球有很多高耸入云的高塔，刚好可以用来做耐摔测试。塔的每一层高度都是一样的，与地球上稍有不同的是，他们的第一层不是地面，而是相当于我们的2楼。

如果手机从第7层扔下去没摔坏，但第8层摔坏了，则手机耐摔指数=7。
特别地，如果手机从第1层扔下去就坏了，则耐摔指数=0。
如果到了塔的最高层第n层扔没摔坏，则耐摔指数=n

为了减少测试次数，从每个厂家抽样3部手机参加测试。

某次测试的塔高为1000层，如果我们总是采用最佳策略，在最坏的运气下最多需要测试多少次才能确定手机的耐摔指数呢？

请填写这个最多测试次数。

注意：需要填写的是一个整数，不要填写任何多余内容。

Analysis

  首先对于一个手机，要测试耐摔指数只能一层一层挨着摔，所以当手机数量为 1 时，测试次数为层数。

  这题的坑在于 最佳策略和最坏运气，只能在最后一个手机测出耐摔指数，也就是子问题要多摔，原问题尽可能少摔。摔第 m 个手机时，在第 k 层的情况可划分为两个子问题，即摔坏和没摔坏，两个子问题取测试次数最多的（最坏运气）；原问题取测试次数最少的。在第 k 层摔坏即上个手机在 [0, k-1] 内摔坏，在第 k 层没摔坏即当前手机在 [k + 1, 1000] 摔坏，也就是剩余的层数。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

#include <bits/stdc++.h>
using namespace std;

// dp[m][f] 表示 m 个手机, f 层时的最多测试次数
int dp[5][1005];

int main() {
    // M: Mobile, F: Floor
    int M = 3, F = 1000;

    // 一个手机时，测试次数等于层数
    for (int f = 1; f <= F; f++) {
        dp[1][f] = f;
    }

    for (int m = 2; m <= M; m++) {
        for (int f = 2; f <= F; f++) {
            dp[m][f] = INT_MAX;

            // 当前手机数量和层数下，获取最少测试次数
            for (int k = 2; k <= f; k++) {
                // 在第 k 层，原问题划分为当前手机摔坏和没摔坏两个子问题，子问题取测试次数最多的
                // 摔坏了则上个手机在[1, k-1]摔坏，没摔坏则当前手机在[k+1, 1000]摔坏，同时测试次数 +1
                dp[m][f] = min(dp[m][f], max(dp[m - 1][k - 1], dp[m][f - k]) + 1);
            }
        }
    }
    cout << dp[3][1000];
}

Tsukkomi

  18 年省赛时候没学过 DP 就没写出来，后来也没再写过。昨天有学弟问我会不会，浏览一遍题还是不会。。。一大早起床就在网上搜题解，总算是有点感觉了。