您当前的位置: 首页 >  蓝桥杯

不牌不改

暂无认证

  • 0浏览

    0关注

    422博文

    0收益

  • 0浏览

    0点赞

    0打赏

    0留言

私信
关注
热门博文

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

不牌不改 发布时间:2022-03-13 18:37:53 ,浏览量:0

题目

题目链接

题解

动态规划。

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             
关注
打赏
1662186765
查看更多评论
0.0365s