【NOI OpenJudge 7627】鸡蛋的硬度

这个题时隔一年多以后我看这个题目还是一脸懵逼,看完题解后恍然大悟。我们设dp[i][j]表示当前有i个楼层,用了j个鸡蛋最坏需要丢多少次,那么转移我们可以通过分解成子问题来做。dp[i][j] = min(dp[i][j], max(dp[k – 1][j – 1], dp[i – k][j]) + 1)。这个max什么意思呢?

这个图蓝色的部分就是第k层红色的部分就是dp[i – k][j],即表示我们在k这一层没有把鸡蛋摔碎,楼上那些需要几次确定答案,绿色的部分表示我们在k这一层鸡蛋被摔碎了,下面k – 1层需要用j – 1个鸡蛋只能用确定了。

#include<algorithm>
#include<iostream>
#include<cstring>
#include<climits>
#include<cstdio>
#include<queue>
#include<cmath>
#include<map>
#define ri register int

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

inline void re(int &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = (x << 1) + (x << 3) + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

int n, m, dp[110][15];

int main()
{
    while(~ scanf("%d%d", &n, &m))
    {
        for(ri i = 1; i <= n; i ++)
            for(ri j = 0; j <= m; j ++)
                dp[i][j] = i;
        for(ri i = 1; i <= n; i ++)
            for(ri j = 1; j <= i; j ++)
                for(ri k = 2; k <= m; k ++)
                    dp[i][k] = min(dp[i][k], max(dp[j - 1][k - 1], dp[i - j][k]) + 1);
        printf("%d\n", dp[n][m]);
    }
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注