[POJ3783]Balls 题解

题目大意

鹰蛋问题.

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

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

正确的解法其实是(DP)

设计状态:

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

1. 蛋碎了,那么还剩下(i-1)个蛋，第(j)层不是(E)层，还有(j-1)层需要确定，可以从(f[i-1][j-1])转移而来.
   　　　
2. 蛋没碎,还剩下(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
" , cas , f[ n ][ m ] ) ;
    }
    return 0 ;
}