题目：

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

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

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

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

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

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

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

如果已知了测试塔的高度，并且采用最佳策略，在最坏的运气下最多需要测试多少次才能确定手机的耐摔指数呢？

输入：

一个整数n（3<n<10000）,表示测试塔的高度。

输出：

输出一个整数，表示最多测试多少次。

思路：

动态规划

2个限制条件，i:手机数量，j：楼高，可以用dp[i][j]表示

一个最佳策略，（从第几层开始扔最好）

一个最差的运气（手机碎还是不碎）

首先列表分析

当只有一个手机时，dp[1][j]=j;

当有两个手机时，在第k层扔，

如果第一次扔掉就碎了，1+dp[1][k-1]

如果第一次扔掉没碎，1+dp[2][j-k]

当有三个手机时，在第k层扔，

如果第一次扔掉就碎了，1+dp[2][k-1]

如果第一次扔掉没碎，1+dp[3][j-k]

总结：

dp[i][j]=min( dp[i][j] , 1 + max( dp[i-1][k-1] , dp[i][j-k] ) )

代码

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
//2个因素，i手机数量，j层数
int n;
int dp[4][10000];
int main() {
    cin >> n;
    for (int j = 0; j <= n; j++) {
        dp[1][j] = j;
        dp[2][j] = j;
        dp[3][j] = j;
    }
    for (int i = 2; i <= 3; i++) {
        for (int j = 0; j <= n; j++) {
            for (int k = 1; k < j; k++) {
                dp[i][j] = min(dp[i][j], 1 + max(dp[i][j - k], dp[i - 1][k - 1]));
            }
        }
    }
    cout << dp[3][n] << endl;
    return 0;
}