4、测试次数
题目 测试次数
思路分析
一开始以为直接二分就行了 算$log_2^n $ 但是…… 如果一个手机的真正耐摔指数为6的话 而二分到了8 它就一定会被摔坏 这样并不能测出来它的耐摔指数
所以测试就得从下往上一个一个测
神特么最优策略 最坏运气 最多次数 题意模糊
最坏的运气下所需的最少测试次数” 是指在考虑所有可能的情况（包括最不利情况）之后，确定耐摔指数所必需的最小测试次数。这是一种优化问题，目的是找到最高效的测试策略，即在最坏情况下测试次数尽可能少。这种情况下的“最少”实际上指的是在所有可能的最坏情况下，我们能做到的最好结果。
使用i台手机在高度为j的楼层测试所需的最多次数 这样的表述可能会引导到一个略有不同的问题定义，可能意味着考虑一种非最优的策略下，进行测试可能达到的最大测试次数。但这并不是我们想要解决的问题。
状态表示
索引i：代表当前剩余可用于测试的手机数量。当一部手机在测试中摔坏时，剩余可用的手机数量减少。
索引j：代表当前考虑的楼层数范围。在问题开始时，j是整个楼的高度，随着测试的进行，j会根据测试结果调整，代表可能的耐摔楼层范围。
值f[i][j]：表示在最坏情况下，使用i部手机在高度为j的楼测试手机的耐摔性时，需要的最少测试次数。
状态转移
状态转移方程考虑了在当前状态下进行一次测试后的所有可能结果，选择这些结果中测试次数最多的一个作为当前状态的值，加上这一次测试，就是f[i][j]的值。具体来说：
当在某一楼层x进行测试时，有两种可能的结果：手机摔坏或没坏。
如果手机摔坏：我们失去了一部手机（手机数量从i减少到i-1），同时楼层的可能范围缩小到x-1层以下（因为我们知道x层能摔坏手机，所以耐摔指数在x-1层或更低）。这对应于状态dp[i-1][x-1]。
如果手机没坏：手机数量保持不变，但我们知道耐摔指数至少是x，因此楼层的可能范围缩小到j-x层（在x+1到j之间）。这对应于状态dp[i][j-x]。
因此，我们对每一种可能的测试楼层x（从1到j）计算以上两种情况的最大值（因为我们考虑的是最坏情况），并在所有楼层x中找到这个最大值最小的情况。最后，f[i][j]就是这个最小的最大值加上这次测试（因此有1 + max(dp[i-1][x-1], dp[i][j-x])）。
这题的状态表示和状态转移…… 确实有点难想
代码实现
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int f[N][N];
int main()
{
int k=3,n=1000;
memset(f,0,sizeof f);
for(int i=1;i<=n;i++){
f[1][i]=i;//一台手机 无所谓策略 最坏情况下测试次数就是楼层数
}
for(int i=2;i<=k;i++){//枚举手机
for(int j=1;j<=n;j++){//枚举楼层
f[i][j]=0x3f3f3f;
for(int x=1;x<=j;x++){//1-j层找最优
//没坏 往上找 j-x 坏了 往下找 x-1
int cost=max(f[i][j-x],f[i-1][x-1])+1;
f[i][j]=min(cost,f[i][j]);
}
}
}
cout<<f[k][n];
return 0;
}
💬 评论