【题目链接】

ybt 1300：鸡蛋的硬度
OpenJudge NOI 2.6 7627:鸡蛋的硬度

【题目考点】

1. 动态规划：区间动规

【解题思路】

扔鸡蛋的决策会构成一个树形的结构。
以下为2层楼扔2个鸡蛋的决策树

小A只能决定每次在哪层楼扔蛋，但不能决定这次扔蛋会不会碎。即在图中每个“第几次扔蛋”的位置，需要选择下面一条实线走下去，而虚线处无法选择。
不同情况下扔蛋的决策合在一起形成一套策略。
无论硬度值为几，在特定的策略下一定可以通过有限次扔蛋测出。即在确定策略后，从根结点到每种硬度的叶子节点，都一定有一条路径。该路径上标有“碎”的虚线的个数，即为使用鸡蛋的个数。必须保证无论鸡蛋硬度如何，该策略下使用鸡蛋的个数都小于等于给定个数m，否则该策略是无效的。
在特定策略下，测出每种硬度时的扔鸡蛋次数是不同的，这些扔鸡蛋次数的最大值，为最坏情况下所需要的扔鸡蛋次数。这里的最坏情况指的是策略固定，鸡蛋硬度变化时的不同情况。每种策略都有一个最坏情况下的扔鸡蛋次数。
比较所有可能的策略的“最坏情况下的扔鸡蛋次数”，有一个策略的“最坏情况下的扔鸡蛋次数”是最小的，该策略为最优策略。

以下为3层楼扔2个鸡蛋的决策树（第一次在3楼扔鸡蛋的情况略）

• 第1次在1楼扔蛋，如果没碎第2次在2楼扔蛋，如果没碎第3次第3楼扔蛋，这就是一个策略。该策略下鸡蛋硬度为0~3的情况都可以测出，在测硬度为2或3的蛋时，需要扔3次，所以这种策略最坏情况下的扔鸡蛋次数为3次。
• 第1次在2楼扔蛋，如果碎了，第2次在1楼扔蛋。如果没碎，第2次在3楼扔蛋。这也是一个策略。该策略下鸡蛋硬度为0~3的情况都可以测出，对于每种硬度的鸡蛋，测出其硬度都只需要2次扔蛋，所以这种策略最坏情况下的扔鸡蛋次数为2次。

因此可以说第二种策略优于第一种策略。该问题求的是：在所有可行的策略中，求出其中“最坏情况下的扔鸡蛋次数”最小的策略。

1. 状态定义

集合：在前n层楼有m个鸡蛋扔鸡蛋的策略
限制：关注的楼层数，拥有的鸡蛋数
属性：扔鸡蛋次数
条件：最小
统计量：扔鸡蛋次数
状态定义：dp[i][j]：在1~i层楼扔最多j个鸡蛋，所有策略中最坏情况下的扔鸡蛋次数最小的策略。
初始状态：
为了求最小值，dp数组初始化为无穷大。
如果在前1~i层最多扔1个鸡蛋。那么只能先在第1层扔，如果碎了鸡蛋的硬度就是0。
不碎的话，再在第2层扔，如果碎了鸡蛋硬度为1，不碎的话，再在第3层扔…
最后一次可能是在第i层扔，如果不碎，鸡蛋硬度为i。
最坏情况下需要扔i次，所以dp[i][1] = i
如果鸡蛋硬度为0，不需要扔鸡蛋就能确定鸡蛋的硬度dp[0][j] = 0

2. 状态转移方程

集合：在1~i层楼扔鸡蛋，共有j个鸡蛋，所有扔鸡蛋的策略。
分割集合：根据这一次在哪一层扔鸡蛋来分割集合
（这就是区间动规问题中枚举分割点的思路）

• 如果在第i层楼扔鸡蛋：
  • 如果没碎，那么鸡蛋硬度为i，扔鸡蛋的次数为1。
  • 如果碎了，那么接下来需要在1~i-1层楼扔鸡蛋，共有j-1个鸡蛋，为了测出鸡蛋硬度扔鸡蛋次数最少为dp[i-1][j-1]，
  • 所以在1~i层为了测硬度最多扔j个鸡蛋的最少扔蛋次数为dp[i][j] = dp[i-1][j-1]+1。
• 如果在第i-1层扔鸡蛋：
  • 如果没碎，那么鸡蛋的硬度可能是i-1~i。接下来需要在第i层扔鸡蛋。这与在第1层扔鸡蛋来确定鸡蛋硬度是0还是1是同样的问题，可用的鸡蛋数为j，因此扔鸡蛋的次数为dp[1][j]+1
  • 如果碎了，那么鸡蛋硬度可能是0~i-2，需要在1~i-2层最多扔j-1个鸡蛋来测出鸡蛋硬度，扔鸡蛋次数为dp[i-2][j-1]+1
  • 最坏情况为以上两种情况下扔蛋次数的最大值，所以在1~i层为了测硬度最多扔j个鸡蛋的最少扔蛋次数为dp[i][j] = max(dp[1][j], dp[i-2][j-1])+1。
• 如果在第i-2层扔鸡蛋：
  • 如果没碎，那么鸡蛋的硬度可能是i-2~i。接下来需要在第i-1~i层扔鸡蛋。这与鸡蛋硬度可能为0~2，需要在第1~2层扔鸡蛋来确定鸡蛋硬度是同样的问题，有j个鸡蛋可用，扔鸡蛋的次数为dp[2][j]+1
  • 如果碎了，那么鸡蛋硬度可能是0~i-3，需要在1~i-3层最多扔j-1个鸡蛋来测出鸡蛋硬度，扔鸡蛋次数为dp[i-3][j-1]+1
  • 最坏情况为以上两种情况下扔蛋次数的最大值，所以在1~i层为了测硬度最多扔j个鸡蛋的最少扔蛋次数为dp[i][j] = max(dp[2][j], dp[i-3][j-1])+1。
    …
• 如果在第1层扔鸡蛋
  • 如果碎了，那么鸡蛋硬度为0，扔鸡蛋次数为1
  • 如果没碎，那么鸡蛋的硬度可能是1~i。接下来需要在第2~i层扔鸡蛋。这与鸡蛋硬度可能为0~i-1，需要在第1~i-1层扔鸡蛋来确定鸡蛋硬度是同样的问题，有j个鸡蛋可用，扔鸡蛋的次数为dp[i-1][j]+1
  • 所以在1~i层为了测硬度最多扔j个鸡蛋的最少扔蛋次数为dp[i][j] =dp[i-1][j]+1。
• 综上，k从1循环到i，在第k层扔鸡蛋
  • 如果碎了，接下来需要在1~k-1层最多扔j-1个鸡蛋来确定高度。dp[i][j] = dp[k-1][j-1]+1
  • 如果没碎，接下来需要在k+1~i层一共i-k层最多扔j个鸡蛋来确定高度。dp[i][j] = dp[i-k][j]+1
  • 因此： dp[i][j] = max(dp[i-k][j], dp[k-1][j-1])+1
• 以上所有情况求出的dp[i][j]取最小值

【题解代码】

解法1：区间动规

#include<bits/stdc++.h>
using namespace std;
int n, m, dp[105][15];//`dp[i][j]`：在1~i层楼扔最多j个鸡蛋，所有策略中最坏情况下的扔鸡蛋次数最小的策略。
int main()
{
    while(cin >> n >> m)
    {
        memset(dp, 0x3f, sizeof(dp));//求最小值，初始化为无穷大 
        for(int i = 1; i <= n; ++i)
            dp[i][1] = i;
        for(int j = 1; j <= m; ++j)
            dp[0][j] = 0;
        for(int i = 1; i <= n; ++i)
            for(int j = 2; j <= m; ++j)
                for(int k = 1; k <= i; ++k)
                    dp[i][j] = min(dp[i][j], max(dp[i-k][j], dp[k-1][j-1])+1);
        cout << dp[n][m] << endl;
    }
    return 0;
}