文档章节

【noi.openjudge】7627 鸡蛋的硬度

LOI_xczhw
 LOI_xczhw
发布于 2016/10/30 09:58
字数 499
阅读 36
收藏 0

dp[i][j]为前i层楼,用j个鸡蛋在最坏情况下要尝试的次数
传子刚开始写了这么一个dp方程

for(int i = 1;i <= n;i ++)
    for(int j = 1;j <= m;j ++)
        dp[i][j] = min(dp[i][j],max(dp[i - 1][j - 1],dp[n - i][j]) + 1);

这个是考虑当我手里有j个鸡蛋的时候怎么检验出i层楼……(意会意会)
先把第j个鸡蛋扔到第i层楼上,{{{{如果碎了,那么就在比它低的几层楼检验(dp[i - 1][j - 1]),因为第j个鸡蛋已经碎了所以只有j - 1个鸡蛋},{如果没碎,就在比它高的楼层检验,将剩下的楼层拿下来,则就是一个有n - i层的楼,因为这个鸡蛋没有碎,所以我们有j个鸡蛋},因为我们要求最坏情况,所以在这一小步要取max},因为我们刚刚拿着第j个鸡蛋扔了一下,所以要加1},因为要求最坏情况下的最小值,所以要取min}(因为的有点乱,请自行括号匹配)
但是我们容易看出,当i比较小的时候,在更新dp[i][j]dp[n - i][j]里面存的并不是真正的值
怎么办?
这一类dp适用于 小问题解决后,大问题才能解决 的类型
因为我想得到有i层高的楼的答案需要用到所以比i小的楼的答案,因此我们需要先枚举我们一共有多少层楼
恩恩

FLOYD

#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 100 + 5;
int dp[MAXN][MAXN];
void init()
{
    for(int i = 1;i <= 100;i ++)
        for(int j = 1;j <= 10;j ++)
            dp[i][j] = i;
    for(int k = 1;k <= 100;k ++)
        for(int i = 1;i < k;i ++)
            for(int j = 2;j <= 10;j ++)
                dp[k][j] = min(dp[k][j],max(dp[i - 1][j - 1],dp[k - i][j]) + 1);
    return;
}
int n,m;
int main()
{
    init();
    while(scanf("%d %d",&n,&m) != EOF)
        printf("%d\n",dp[n][m]);
    return 0;
}

© 著作权归作者所有

LOI_xczhw
粉丝 1
博文 79
码字总数 42567
作品 0
莱芜
私信 提问
Ubuntu grub2介绍

Ubuntu grub2简介   从Ubuntu 9.10起,grub2就已经是默认的BootLoader了。这里简要说要Ubuntu的grub2和其他发行版不一样的地方。   对于所有的OS启动项,CentOS全都显示在一个grub选择界...

BookShu
2016/12/11
135
0
2018 年力扣高频算法面试题汇总-难题记录-鸡蛋掉落

题目描述: 你将获得 个鸡蛋,并可以使用一栋从 到 共有 层楼的建筑。 每个蛋的功能都是一样的,如果一个蛋碎了,你就不能再把它掉下去。 你知道存在楼层 ,满足 任何从高于 的楼层落下的鸡蛋...

chenjx85
03/13
0
0
Spark FPGrowth关联规则算法

Spark.mllib 提供并行FP-growth算法,这个算法属于关联规则算法【关联规则:两不相交的非空集合A、B,如果A=>B,就说A=>B是一条关联规则,常提及的{啤酒}-->{尿布}就是一条关联规则】,经常用...

penngo
03/11
153
0
多线程通信

生产者/消费者模式是一个经典的线程同步以及通信的模型。 假设有这样一种情况,有一个盘子,盘子里只能放一个鸡蛋,A线程专门往盘子里放鸡蛋,如果盘子里有鸡蛋,则一直等到盘子里没鸡蛋,B...

Heinrich_Chen
2016/01/21
160
0
这鸡蛋真难吃

有些人的逻辑是很奇怪的。 网友若昔难得就归纳出了几种。如此经典的内容,我一定要转载, 希望大家集思广益,一起来补充。 ============= A:这鸡蛋真难吃。 B:隔壁家那鸭蛋更难吃,你咋不说...

阮一峰
2008/07/26
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Spring使用ThreadPoolTaskExecutor自定义线程池及实现异步调用

多线程一直是工作或面试过程中的高频知识点,今天给大家分享一下使用 ThreadPoolTaskExecutor 来自定义线程池和实现异步调用多线程。 一、ThreadPoolTaskExecutor 本文采用 Executors 的工厂...

CREATE_17
今天
5
0
CSS盒子模型

CSS盒子模型 组成: content --> padding --> border --> margin 像现实生活中的快递: 物品 --> 填充物 --> 包装盒 --> 盒子与盒子之间的间距 content :width、height组成的 内容区域 padd......

studywin
今天
7
0
修复Win10下开始菜单、设置等系统软件无法打开的问题

因为各种各样的原因导致系统文件丢失、损坏、被修改,而造成win10的开始菜单、设置等系统软件无法打开的情况,可以尝试如下方法解决 此方法只在部分情况下有效,但值得一试 用Windows键+R打开...

locbytes
昨天
8
0
jquery 添加和删除节点

本文转载于:专业的前端网站➺jquery 添加和删除节点 // 增加一个三和一节点function addPanel() { // var newPanel = $('.my-panel').clone(true) var newPanel = $(".triple-panel-con......

前端老手
昨天
8
0
一、Django基础

一、web框架分类和wsgiref模块使用介绍 web框架的本质 socket服务端 与 浏览器的通信 socket服务端功能划分: 负责与浏览器收发消息(socket通信) --> wsgiref/uWsgi/gunicorn... 根据用户访问...

ZeroBit
昨天
10
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部