2018年蓝桥杯C++ B组省赛-测试次数

题目

题目链接

题解

动态规划。

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