题目
题目链接
题解动态规划。
dp[i][j]
表示使用i
部手机从j
层高的塔验证采用最佳策略,在最坏的运气下测试的次数。
状态转移:
-
当只有一部手机时,最坏情况下我们需要从第 1 层一直测试到第
j
层楼,那么一共测试j
次,dp[1][j] = j
-
当拥有两部或两部以上手机时,这时我们需要考虑最优策略。
当前我们在第 k 层测试,用到第 i 部手机时,测试会出现两种情况
① 摔坏:如果在第
k
层摔坏了,那么我们只需要用剩下的i - 1
部手机去测试剩下的k - 1
层楼,即dp[i - 1][k - 1]
② 未摔坏:如果在第k
层没有摔坏,那么我们只需要用i
部手机去测试剩下的n - k
层楼,即dp[i][n - k]
因为在这个测试过程中,我要保证运气最坏,因此 dp[i][k] = max(dp[i - 1][k - 1], dp[i][n - k]) + 1
其中: +1 是指 无论当前这次测试摔坏、没摔坏,我都进行了一次测试 max 的目的 是要在测试过程中保证运气最坏,即最坏情况
故,状态转移方程:dp[i][j] = min(d[i][j], max(dp[i - 1][k - 1], dp[i][n - k]) + 1)
其中min是时刻要保证最优策略
代码//
#include
using namespace std;
int n = 1000;
int dp[5][1010];
int main()
{
for (int i = 0;i
关注
打赏
最近更新
- 深拷贝和浅拷贝的区别(重点)
- 【Vue】走进Vue框架世界
- 【云服务器】项目部署—搭建网站—vue电商后台管理系统
- 【React介绍】 一文带你深入React
- 【React】React组件实例的三大属性之state,props,refs(你学废了吗)
- 【脚手架VueCLI】从零开始,创建一个VUE项目
- 【React】深入理解React组件生命周期----图文详解(含代码)
- 【React】DOM的Diffing算法是什么?以及DOM中key的作用----经典面试题
- 【React】1_使用React脚手架创建项目步骤--------详解(含项目结构说明)
- 【React】2_如何使用react脚手架写一个简单的页面?