[POJ3783]Balls 题解

题目大意

鹰蛋问题.$

n$个蛋，$m$层楼. 存在一层楼$E$,使得$E$以及$E$以下的楼层鹰蛋都不会摔碎，问最坏情况下最少多少次能够知道$E$.

非常经典的模型，初看题目根本想不到用什么方法做，一开始可能会想到二分答案、单调队列和一些线性的东西。但是明确的说：这些都是不可行的！

正确的解法其实是$DP$

设计状态:

$f[i][j]$表示$i$个蛋，确定$j$层楼的$E$的答案. 如果当前在第$k$层扔蛋,两种可能：

　　

蛋碎了,那么还剩下$i-1$个蛋，第$j$层不是$E$层，还有$j-1$层需要确定，可以从$f[i-1][j-1]$转移而来.

　　　
蛋没碎,还剩下$i$个蛋，第$k$层以下都不可能是$E$层了，还剩下$j-k$层需要确定.那么从$f[i][j-k]$转移而来. 注意，这里的从上往下数$j-k$层和从下往上数$j-k$层本质上是没有区别的,所以可以把这$j-k$层看作一个新的高$j-k$层的楼.

　　　

接着就是重中之重了,如何转移？事情总是朝着最坏的方向发展的. 第$k$层会不会摔碎实际上是不能确定的！要从最坏的状态转移而来！那么状态转移方程就是：$f[i][j]=min(max(f[i-1][j-1],f[i][j-k])+1,f[i][j])$.

然后就可以很快写出代码：

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std ;

int T , cas , n , m ;

int f[ 3005 ][ 3005 ] ;

inline void solve () {

    memset ( f , 0x3f , sizeof ( f ) ) ;

    for ( int i = 1 ; i <= n ; i ++ ) f[ i ][ 0 ] = 0 ;

    for ( int i = 1 ; i <= m ; i ++ ) f[ 1 ][ i ] = i ;

    for ( int i = 1 ; i <= n ; i ++ ) {

        for ( int j = 1 ; j <= m ; j ++ ) {

            for ( int k = 1 ; k <= j ; k ++ )

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

        }

    }

}

signed main () {

    scanf ( "%d" , &T ) ;

    while ( T -- ) {

        scanf ( "%d%d%d" , &cas , &n , &m ) ;

        solve () ;

        printf ( "%d %d\n" , cas , f[ n ][ m ] ) ;

    }

    return 0 ;

}

巴特西

[POJ3783]Balls 题解

题目大意

最新文章

热门文章