Openjudge#7627:鸡蛋的硬度

自从知道CodeForces之后我就没怎么看Openjudge了。尤其是现在还知道了UVA这一老题库,更鄙视Openjudge了,连题解都没有,也看不了别人的程序。昨天刘励行问了我这道2.6的动规题,我却一时半会答不上来,自觉惭愧。看来只有写一篇解题报告才能对得起自己了。

原题链接

这个题意需要好好梳理一下。我一开始不太明白的地方就是,为什么加了鸡蛋可以减少尝试次数?而且,鸡蛋是不是摔碎了会怎么样?还十分容易把这题和二分搞混,但题目中也明确说明了这不是二分。我一开始还以为这个人有多个伙伴一起帮他扔,后来发现是一个人!想想就好累啊。不过这和题目没关系。

梳理之后发现,鸡蛋摔碎了就不能再扔了。之后能够测试的鸡蛋就少了。但是如果扔出一次鸡蛋,就可以得到一点信息:这个鸡蛋的硬度是在该楼层上面还是在该楼层下面。所以从这里可以分析出,假设在第k层扔出鸡蛋,扔一次鸡蛋之后要分两种情况,一种是摔碎了,一种是没摔碎。如果摔碎了,那么鸡蛋的硬度就<k,否则硬度就≥k。还有一个值得注意的是,摔碎了的话鸡蛋会变少一个。判断出来了之后就形成了一个子问题,在更小的楼层里判断出鸡蛋的硬度。对两种情况取一个最大值,才能保证计算得到的是最坏情况时的取值。我还以为需要考虑最优策略,结果巧妙的绕过去了。这样就可以开始应用动态规划了啊!

设f[i][j]的值为在k层楼中,有j个鸡蛋,要确定鸡蛋的硬度时最坏情况所需的最小步数。故状态转移方程为:

f[i][j]=min{max{f[k-1][j-1]/鸡蛋碎了/,f[j-k][j]/鸡蛋没碎/}}+1

边界条件:f[i][0]=i。这是从题目中知道的,挺有道理,照搬过来。

然后我就发现了一个问题。这个问题让我第一次不能AC。在代码实现中,这个+1放在哪里?我是先初始化f[i][j]为i,因为不可能超过i次;然后寻找最小值,最后++。这时问题出现了,假如说没有比i更小了的呢?那么岂不就成i+1了?

所以我在程序中的实现改为

f[i][j]=min(f[i][j],1+max(f[i-k][j],f[k-1][j-1]))

AC之。

下面附上AC源代码:

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
/*
core:
    f[i][j]=min{max{f[i-k][j],f[k-1][j-1]}}+1
*/
int main(){
    int f[105][15],n,m;
    for(int i=0;i<105;i++){
        f[i][0]=1<<31;
        f[i][1]=i;
        for(int j=2;j<15;j++){
            f[i][j]=i;
            for(int k=1;k<=i;k++){
                f[i][j]=min(f[i][j],1+max(f[i-k][j],f[k-1][j-1]));
            }
        }
    }
    while(cin>>n>>m){
        cout<<f[n][m]<<endl;
    }
}

快六点四十了,我且先去吃饭。

avatar
Kerry Su