鸡蛋掉落问题（进阶版：带楼层限制的鸡蛋掉落）的变种：带成本限制的鸡蛋掉落

问题描述
你拥有 k 枚相同的鸡蛋，并希望测试从一座 n 层高的建筑中鸡蛋在哪一层楼及以上会摔碎（从第 1 层到第 n 层，假设从某一层 f 及以上（f 从 0 到 n，f=0 表示鸡蛋在任何楼层都不会摔碎，f=n 表示鸡蛋在任何楼层都会摔碎）扔下鸡蛋会摔碎，而低于 f 的楼层鸡蛋不会摔碎）。
每次操作，你可以选择从某一层 x 扔下鸡蛋：

• 如果鸡蛋碎了，那么你会损失这枚鸡蛋，并且需要测试更低的楼层（1 到 x-1）。
• 如果鸡蛋没碎，那么鸡蛋可以继续使用，并且你需要测试更高的楼层（x+1 到 n）。

与经典鸡蛋掉落问题不同，本题新增一个成本限制：每次扔鸡蛋的操作成本与其所在的楼层 x 成正比，假设成本为 x。也就是说，从第 x 层扔下鸡蛋的成本是 x 单位。
你需要在总操作成本不超过 C 的前提下，找到最少的操作次数（即扔鸡蛋的次数）的最坏情况下的最小值。或者说，在成本预算 C 内，你至少需要多少次扔鸡蛋操作，才能确保找出临界楼层 f？

你需要设计一种策略，在总成本不超过 C 的情况下，在最坏情况下所需的最少操作次数。如果无法在成本 C 内完成测试，则返回 -1。

输入格式
三个整数：n（楼层数，1 ≤ n ≤ 1000），k（鸡蛋数，1 ≤ k ≤ 100），C（总成本限制，1 ≤ C ≤ 10000）。

输出格式
一个整数，表示在成本限制 C 内，在最坏情况下所需的最少操作次数，如果无法完成则返回 -1。

例子
例1：
输入：n = 6, k = 2, C = 10
输出：3
解释：
一种可能策略：
第一次从第 3 层扔，成本 3，如果碎了则用剩下的 1 个鸡蛋从第 1 层开始逐层测试（成本 1+2=3）；如果没碎则从第 5 层扔（成本 5），依此类推。
在最坏情况下总成本不超过 10，操作次数为 3。

例2：
输入：n = 100, k = 1, C = 1000
输出：100
解释：只有一个鸡蛋，只能从低到高逐层测试，最坏情况需要 100 次操作，总成本是 1+2+...+100=5050>1000，但题目要求总成本不超过 C，实际上 1000 的成本足够 100 次操作（因为逐层测试到第 100 层的总成本是 5050>1000，所以无法在成本 1000 内完成测试？这里需要精确计算，如果成本 1000 不足以支持 100 次操作，则可能输出 -1）。这提示我们成本限制可能使得策略不可行。

问题解析
这是经典鸡蛋掉落问题的扩展，加入了成本限制。经典问题是：用 k 个鸡蛋，最少操作次数（扔的次数）在最坏情况下确定 f。经典问题的动态规划状态 dp[m][k] 表示用 k 个鸡蛋，最多允许 m 次操作，能确定的最大楼层数 n。
本题反过来：给定 n,k,C，求最少操作次数 m，使得存在策略在 m 次操作内、总成本不超过 C 时能确定 f。

状态设计思路
我们可以定义 dp[m][k] 表示在最多 m 次操作，最多 k 个鸡蛋，总成本不超过 C 的情况下，能确定的最大楼层数 n。
但这里成本是变化的，因为每次选择的楼层 x 会影响成本，所以我们需要在状态中加入当前剩余成本。
更直接的做法：
定义 dp[m][k][c] 表示在剩余成本 c 时，用最多 m 次操作，k 个鸡蛋，能确定的最大楼层数。但这样状态维度太大（m 可达 1000，k 100，c 10000）。

另一种思路
我们换个角度：定义 f(m,k) 表示在最多 m 次操作，k 个鸡蛋，总成本预算无限时能确定的最大楼层数（经典问题结果）。经典递推：
f(m,k) = f(m-1,k-1) + 1 + f(m-1,k)
含义：第一次从第 x 层扔，如果碎了，则下面还能用 m-1 次操作和 k-1 个鸡蛋测 x-1 层；如果没碎，则上面还能用 m-1 次操作和 k 个鸡蛋测 f(m-1,k) 层。所以 x 选在中间使得两边平衡，但这里 x 的值会影响成本，所以我们不能任意选 x，必须让成本满足约束。

在经典问题中，第一次扔的楼层 x 是 f(m-1,k-1)+1，这样两边可测楼层数一致。但在成本限制下，我们需要选择 x 使得成本不超，并且可测总楼层最大。

重新定义状态
我们直接求最小操作次数 m，使得在成本 C 内能测 n 层。
设 dp[i][j] 表示用 i 次操作，j 个鸡蛋，在成本不超过 C 的前提下，能确定的最大楼层数。
递推时，我们考虑第一次扔的楼层 t（1 ≤ t ≤ 某个上限），则：
如果碎了，剩下 i-1 次操作，j-1 个鸡蛋，剩余成本 C - t，能测的楼层数为 dp[i-1][j-1]（在成本预算 C-t 下），注意这个 dp 应该是在剩余成本下能测的最大楼层数，但我们的 dp 状态是全局预算 C 下的，所以我们需要在递推时考虑剩余成本。

为了将成本纳入状态，可以这样：定义 dp[i][j][c] 表示用 i 次操作，j 个鸡蛋，总成本上限 c 时，能确定的最大楼层数。
转移方程：
dp[i][j][c] = max_{1 ≤ t ≤ min(c, 某个上限)} { 1 + dp[i-1][j-1][c-t] + dp[i-1][j][c-t] }
这里 1 是因为 t 层本身测试一次，但注意 dp 表示能区分的楼层数，实际上递推公式是：
可测最大楼层 = dp[i-1][j-1][c-t] (下面部分) + dp[i-1][j][c-t] (上面部分) + 1（测试的 t 层本身）。

初始条件：dp[0][j>0][c] = 0（0 次操作无法测任何层），dp[i≥0][0][c] = 0（没有鸡蛋无法测试）。
对于 i=1，j≥1，c≥1：只能测试一层，dp[1][j][c] = 1（如果 c≥1）。

我们需要找到最小的 i，使得 dp[i][k][C] ≥ n。

状态压缩优化
c 的范围是 0 到 C，i 范围是 0 到 m_max，m_max 不会超过 n（因为最坏逐层测试需要 n 次操作），但可能更小。
我们可以从 i=1 开始增加，计算 dp[i][j][c]，直到 dp[i][k][C] ≥ n 或 i 超过某个上限（比如 1000）。

算法步骤

1. 初始化 dp[j][c] 为 0 数组（维度 k+1 行，C+1 列），用来表示用 j 个鸡蛋，成本 c 时，最多可测楼层数，但这里我们还需要操作次数 i 的维度。我们用二维滚动数组 dp[j][c] 表示当前 i 次操作下的可测最大楼层数。我们需要用临时数组存储上一次 i-1 的结果。

2. 实际上，我们用 dp_prev[j][c] 表示 i-1 次操作，j 个鸡蛋，成本上限 c 时的最大可测楼层数。
   转移时，dp_cur[j][c] 从 dp_prev 转移而来：
   对于每个 j (1 到 k)，c (1 到 C)，我们枚举第一次扔的楼层 t (1 到 c，因为成本 t 必须 ≤ c)：
   可测楼层 = 1 + dp_prev[j-1][c-t] + dp_prev[j][c-t]，这里 dp_prev[j-1][c-t] 是下面可测楼层数，dp_prev[j][c-t] 是上面可测楼层数。
   但注意：如果 t 大于当前 c 则不可能。

3. 枚举 t 时，我们取所有 t 下的最大值，但 t 最大为 c，且 t 不能超过当前可测楼层的上限（否则无意义）。

4. 计算完 dp_cur 后，检查 dp_cur[k][C] ≥ n 则返回当前的 i。

5. 如果 i 达到 n 仍未满足，说明在成本 C 内无法完成，返回 -1。

复杂度
状态数 O(kC)，每个状态枚举 t 需要 O(C)，总 O(kC^2) 太大。C 可达 10000，不可行。

优化枚举 t
观察递推公式：
dp[i][j][c] = max_{1≤t≤c} { 1 + dp[i-1][j-1][c-t] + dp[i-1][j][c-t] }
令 A = dp[i-1][j-1][c-t]，B = dp[i-1][j][c-t]，则我们需要最大化 A+B。
注意 A 和 B 是随着 c-t 变化而变化的，t 从 1 到 c，c-t 从 c-1 到 0。
如果我们定义 g(t) = 1 + A + B，其中 A 和 B 是 c-t 的函数，这个函数通常随着 c-t 增大而增大（因为成本越多，可测楼层越多），但 t 本身在增加时 c-t 减少，所以 g(t) 可能不是单调的。
但经典鸡蛋掉落中，最优 t 是让 A 和 B 平衡，这里类似。
我们可以用二分法或双指针优化枚举 t 的过程，但 A 和 B 是离散的，不好直接二分。
不过本题 n 比较小（1000），我们可以限制 i 的上限，比如 i 不超过 1000，然后对于给定的 i,j，我们可以用双指针优化：
令剩余成本 r = c-t，则 t = c-r，我们需要最大化 1 + dp_prev[j-1][r] + dp_prev[j][r]，其中 0 ≤ r ≤ c-1。
所以我们可以预先计算出所有 r 对应的值，然后取最大值。但 r 是从 0 到 c-1，我们只需遍历 r 一次，就可以得到最大值，所以枚举 t 的复杂度从 O(c) 降为 O(c) 不变？不对，我们这里枚举 t 就是枚举 r，所以就是 O(c)。但我们可以用前缀最大值优化吗？不行，因为 dp_prev[j-1][r] 和 dp_prev[j][r] 的和不是单调的。

实际计算可行范围
鉴于 n 较小，我们可以换一种思路：直接计算 dp[i][j] 表示用 i 次操作，j 个鸡蛋，在最优策略下所需的最小总成本，来测 n 层楼。但这样状态意义反了。

更简单的方法
我们回到经典鸡蛋掉落的思路：f(m,k) 表示 m 次操作 k 个鸡蛋能测的最大楼层数。
现在加入成本，设 g(m,k) 表示 m 次操作 k 个鸡蛋，在最优策略下所需的最小总成本，来确保能测 f(m,k) 层楼。
递推：g(m,k) = min_{1≤t≤f(m-1,k-1)+1} { t + max(g(m-1,k-1), g(m-1,k)) }。
但这样假设每次测试成本 t 是加在最坏情况路径上的，实际上成本是路径上选择的楼层之和，最坏情况下成本是沿着某个分支的楼层和，所以 g 应该表示最坏情况下的最小成本。
我们定义 h(m,k) 表示 m 次操作，k 个鸡蛋，在最坏情况下所需的最小成本上限，使得能测至少 n 层。但我们不知道 n，所以不好定义。

最后采用二分+DP验证
二分操作次数 m，判断是否存在策略在 m 次操作，k 个鸡蛋，总成本 ≤ C 时测 n 层楼。
如何判断？用 DP 计算 dp[m][k] 表示在 m 次操作，k 个鸡蛋，总成本限制 C 时能测的最大楼层数。
dp 的计算可以用递归+记忆化搜索，状态 (m,k,c) 表示剩余操作次数 m，剩余鸡蛋 k，剩余成本 c，返回能测的最大楼层数。
递归函数 f(m,k,c)：
如果 m=0 或 c<0 或 k=0，返回 0。
枚举第一次扔的楼层 t 从 1 到 c（因为成本 t 必须 ≤ c）：
结果 = 1 + f(m-1,k-1,c-t) + f(m-1,k,c-t)
取最大值返回。
用记忆化搜索，状态数 mkc 仍很大，但 m 是二分的，范围 1 到 n，c 是 C，最大 10000，太大。

优化
注意到 f(m-1,k-1,c-t) 和 f(m-1,k,c-t) 关于 t 是递减的吗？不，因为 c-t 减少，这两个值一般也减少，所以总的 1 + A + B 随着 t 增加（c-t 减少）是递减的，所以最大值在 t 最小时取得，即 t=1。这意味着低成本时，我们应尽量从低楼层开始测试，以减少成本。但这样测的楼层数会少，因为 t 小则分割的上下部分不均衡。
实际上，为了最大化可测楼层数，我们希望 t 在满足成本约束下尽可能大，使得两边平衡。但 t 越大，成本越高，可能使得剩余成本不足。

最终算法采用动态规划+贪心选择 t
我们直接用第一种方法的状态 dp[i][j][c]，但优化枚举 t 的方法：
对于固定的 i,j,c，dp[i][j][c] 的递推公式中，dp[i-1][j-1][c-t] 和 dp[i-1][j][c-t] 都是关于 c-t 非递减的，所以 1+两者之和关于 t 是递减的（因为 c-t 随 t 增加而减少），所以最大值在 t 尽可能小时取得，即 t=1。但这会导致可测楼层数很小，不符合实际。我们需要重新审视。

正确思路
经典鸡蛋掉落中，第一次选择楼层 t 是为了平衡碎与不碎后剩下的可测楼层数，使得总可测楼层数最大。加入成本限制后，t 的选择不仅要平衡，还要考虑成本。实际上，我们可以用 DP 计算 dp[i][j] 表示用 i 次操作，j 个鸡蛋，在最优策略下所需的最小最坏情况总成本，来测至少 n 层。
然后我们找最小的 i 使得 dp[i][k] ≤ C。

定义 dp[i][j] 为用 i 次操作，j 个鸡蛋，能测的最大楼层数所需的最小成本上限。
递推：dp[i][j] = min_{1≤t≤n} { t + max(dp[i-1][j-1], dp[i-1][j]) }，但要保证 t 的选择使得可测楼层数达到 n？这里矛盾，因为我们不知道 n。

最终采用二分+验证
二分 m 从 1 到 n，检查是否能在 m 次操作，k 个鸡蛋，成本 C 内测 n 层。
检查函数 check(m)：
用 DP 计算 f[i][j] 表示 i 次操作，j 个鸡蛋，在成本限制 C 内能测的最大楼层数。
转移：f[i][j] = max_{1≤t≤C} { 1 + f[i-1][j-1] + f[i-1][j] }，但这里 t 是成本，f 是楼层数，这样不对，因为 f[i-1][*] 是在剩余成本 C-t 下计算的，所以我们需要状态包含成本。

鉴于复杂度，本题通常限制 n,k,C 较小，可采用以下简化算法
由于 n ≤ 1000, k ≤ 100, C ≤ 10000，我们可以用 DP 状态 dp[i][j] 表示用 i 次操作，j 个鸡蛋，在总成本不超过 C 时能确定的最大楼层数。但这样没有成本维度，无法控制成本。

因此，最终我们采用三维 DP，但优化枚举 t 为枚举剩余成本
设 dp[i][j][c] 表示 i 次操作，j 个鸡蛋，成本上限 c 时能测的最大楼层数。
初始化：dp[0][][] = 0, dp[][0][] = 0。
转移：
dp[i][j][c] = max_{1≤t≤c} { 1 + dp[i-1][j-1][c-t] + dp[i-1][j][c-t] }
但这样枚举 t 是 O(c) 的，总 O(mkC^2) 太大。

优化
对于固定的 i,j，dp[i-1][j-1][x] 和 dp[i-1][j][x] 都是关于 x 单调不降的，所以 1 + dp[i-1][j-1][c-t] + dp[i-1][j][c-t] 关于 t 是单调不增的（因为 c-t 随 t 增加而减少），所以最大值在 t 最小处取得，即 t=1。但这显然不对，因为 t 小会导致可测楼层数小。实际上，为了让可测楼层数最大，我们希望 t 在 dp[i-1][j-1][c-t] 和 dp[i-1][j][c-t] 之间平衡，但单调性表明 t 越小，c-t 越大，dp 值越大，所以总和越大。所以最优 t 就是 1。

这似乎与直觉矛盾，但仔细想：在成本限制下，为了最大化可测楼层数，我们应该从低楼层开始测试，以节省成本给后面更多的操作，所以 t=1 确实可能是最优的。但这样测的楼层数会很少，因为第一次测试的楼层太低，上面部分很大，下面部分很小，不均衡。但公式中上面部分用 dp[i-1][j][c-t] 表示，如果 t 小，c-t 大，上面部分可测楼层数可能很大，下面部分 dp[i-1][j-1][c-t] 也大，所以总和可能更大。
所以我们直接取 t=1 即可得到最大值。

简化后的递推
dp[i][j][c] = 1 + dp[i-1][j-1][c-1] + dp[i-1][j][c-1]
但需注意 c≥1。

这样，我们可以用 O(mkC) 的时间计算。

然后找最小的 i 使得 dp[i][k][C] ≥ n。

验证
用例子 n=6,k=2,C=10 测试：
初始化 dp[0][][]=0。
i=1,j=1,c 从 1 到 10：dp[1][1][c] = 1（因为只能测 1 层，从 1 层扔一次，成本 1）。
i=1,j=2,c≥1：dp[1][2][c] = 1。
i=2,j=1：dp[2][1][c] = 1 + dp[1][0][c-1] + dp[1][1][c-1] = 1 + 0 + 1 = 2（c≥2）。
i=2,j=2,c=2：dp[2][2][2] = 1 + dp[1][1][1] + dp[1][2][1] = 1+1+1=3。
继续计算 i=3,j=2,c=10：
dp[3][2][10] = 1 + dp[2][1][9] + dp[2][2][9]。
计算 dp[2][1][9] = 1 + dp[1][0][8] + dp[1][1][8] = 1+0+1=2（实际上逐层测试，2 次操作 1 个鸡蛋成本 9 最多测 2 层？因为从 1 层开始，如果没碎再从 2 层，总成本 1+2=3≤9，所以可测 2 层，正确）。
dp[2][2][9] 需要递推：dp[2][2][9] = 1 + dp[1][1][8] + dp[1][2][8] = 1+1+1=3。
所以 dp[3][2][10] = 1+2+3=6 ≥ n=6，所以 i=3 满足。

最后答案
我们只需计算 dp[i][k][C] 直到 ≥ n 或 i 超过 n（因为最多 n 次操作一定可以）。

算法步骤总结

1. 初始化 dp[0][j][c]=0，dp[i][0][c]=0。
2. 对于 i 从 1 到 n：
   对于 j 从 1 到 k：
   对于 c 从 1 到 C：
   如果 c < 1，dp[i][j][c] = 0
   否则 dp[i][j][c] = 1 + dp[i-1][j-1][c-1] + dp[i-1][j][c-1]
3. 如果 dp[i][k][C] ≥ n，返回 i。
4. 如果循环结束未找到，返回 -1。

复杂度 O(nkC)，n=1000,k=100,C=10000 是 1e9，太大，需要优化。
但注意 c 从 1 到 C 的循环中，dp 只依赖于 c-1，所以可以压缩为一维数组。
而且 n 可能不需要到 1000，因为操作次数不会很大。

最终代码框架

int superEggDropCost(int n, int k, int C) {
    vector<vector<int>> dp(k+1, vector<int>(C+1, 0));
    for (int m = 1; m <= n; m++) {
        vector<vector<int>> ndp = dp;
        for (int j = 1; j <= k; j++) {
            for (int c = 1; c <= C; c++) {
                ndp[j][c] = 1 + dp[j-1][c-1] + dp[j][c-1];
                if (ndp[j][c] > n) ndp[j][c] = n; // 截断
            }
        }
        if (ndp[k][C] >= n) return m;
        dp = ndp;
    }
    return -1;
}

但这里 ndp[j][c] 用了 dp[j-1][c-1] 和 dp[j][c-1]，而 dp 是上一轮 m-1 的结果，所以正确。

用例子测试可得结果符合。