题目描述:

x星球的居民脾气不太好,但好在他们生气的时候唯一的异常举动是:摔手机。

各大厂商也就纷纷推出各种耐摔型手机。x星球的质监局规定了手机必须经过耐摔测试,并且评定出一个耐摔指数来,之后才允许上市流通。

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

如果手机从第7层扔下去没摔坏,但第8层摔坏了,则手机耐摔指数=7。

特别地,如果手机从第1层扔下去就坏了,则耐摔指数=0。

如果到了塔的最高层第n层扔没摔坏,则耐摔指数=n

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

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

请填写这个最多测试次数。
注意:需要填写的是一个整数,不要填写任何多余内容。

思路:dp

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
30
31
32
33
34
35
36
37
38
39
40
41
42
/*
定义:F[i][j] 为还有i楼未确认,j部手机时的测试次数
运气最差:测试次数总是往着最多的方向发展
策略最佳:在各个最差的运气导致的结果中选择最小的那个

边界:
F[0][?] = 0;没有楼层 不需要测试
F[?][0] = 0;没有手机 不需要测试
F[n][1] = n;只有一部手机 有多少楼就需要测多少次
F[1][n] = 1;只有一层楼 不论有多少手机都只需要测试一次

初始化:F[i][j] = i; 最坏的情况 有多少楼测多少次

状态转移方程:
F[i][j] = min( F[i][j] , max(F[floor-1][j-1],F[i-floor][j])+1 ) for floor in 1..i

max(F[floor-1][j-1],F[i-floor][j]):取运气最差的情况
*/
#include<bits/stdc++.h>
using namespace std;

int F[1005][5];

int main(){
/*边界初始化*/
for(int i=0; i <= 1000; i++){
for(int j = 1; j <= 3; j++){
F[i][j] = i;
}
}

/* dp */
for(int i = 1;i <= 1000;i++){
for(int j = 2; j <= 3; j++){
for(int floor = 1; floor <= i; floor++){//选取最佳策略(开始楼层)
F[i][j] = min( F[i][j] , max(F[floor-1][j-1],F[i-floor][j]) + 1);
}
}
}
cout<<F[1000][3]<<endl; //Prints:19
return 0;
}

故此题答案为: 19