怎么创办自己的网站,河南手机网站设计,二手书交易网站开发毕业设计,outlook企业邮箱注册申请测试次数 - 蓝桥云课 (lanqiao.cn)
题目描述 题目分析
对于本题我们可以使用动态规划来分析
dp[i][j]代表剩余i层#xff0c;j台手机的情况下对应的测试数量
分类进行讨论一下#xff1a;
1.当只剩下一台手机的时候#xff0c;只能从第一层一层一层往上尝试#xff0c…测试次数 - 蓝桥云课 (lanqiao.cn)
题目描述 题目分析
对于本题我们可以使用动态规划来分析
dp[i][j]代表剩余i层j台手机的情况下对应的测试数量
分类进行讨论一下
1.当只剩下一台手机的时候只能从第一层一层一层往上尝试尝试到第几层摔坏就是几
2.当j 2假设剩余k层总层数为n,dp[k][2]可以分为以下两种情况 ①摔坏 dp[k][2] dp[k - 1][1]; ②没摔坏 dp[k][2] dp[n - k][2] //n - k相当于把下面的k层全部砍掉
当j 3同理
由于考虑的是最坏的情况所以我们需要在手机摔坏和没摔坏这两种情况中取到最大的测试次数由于我们要考虑最坏的最优情况所以我们要在每层最大的里面选择最小的
#includebits/stdc.h
using namespace std;
const int N 2e3 10;
int dp[N][N];
int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int l 1, r 1000;for(int i 1; i 1000; i )dp[i][1] i;//第一部手机 for(int j 2; j 3; j )//第二和第三部手机 {for(int i 1; i 1000; i ){dp[i][j] 1e9 10;for(int k 1; k i; k )//手机在第k层是否摔坏 {dp[i][j] min(max(dp[k - 1][j - 1], dp[i - k][j]) 1, dp[i][j]); }}}cout dp[1000][3];return 0;
}
