首页 > 代码库 > zoj 2972 - Hurdles of 110m

zoj 2972 - Hurdles of 110m

题目:110米栏,运动员可以用三种状态跑,1状态耗体力且跑得快,2状态不消耗体力,3状态恢复体力且跑得慢。

           体力上限是M,且初始满体力,现在想知到最小的时间跑完全程。

分析:dp,完全背包。题目是一个物品体积可能为负数的背包,求背包即可。

           不过,因为物品体积可能是负数,所以不管哪个方向背包都有后效性,直接用二维避免后效性。

           转移方程:F(i,j)= min(F(i-F1,j)+ T1,F(i-1,j)+ T2,F(i+F2,j)+T3)。 

说明:(2011-09-19 01:23)。

#include <iostream>
#include <cstdlib>

using namespace std;

int F[ 111 ][ 111 ];
int T1[ 111 ];
int T2[ 111 ];
int T3[ 111 ];
int F1[ 111 ];
int F2[ 111 ];

int dp( int N, int M )
{
    for ( int i = 0 ; i <= N ; ++ i )
    for ( int j = 0 ; j <= M ; ++ j )
        F[ i ][ j ] = 0xffffff;
    
    for ( int i = 0 ; i <= M ; ++ i )
        F[ 0 ][ i ] = 0;
    
    for ( int i = 1 ; i <= N ; ++ i ) {
        /* 第一状态 */
        for ( int j = F1[ i ] ; j <= M ; ++ j )
            if ( j <= M && F[ i ][ j-F1[ i ] ] > F[ i-1 ][ j ] + T1[ i ] )
                F[ i ][ j-F1[ i ] ] = F[ i-1 ][ j ] + T1[ i ];
        /* 第二状态 */
        for ( int j = 0 ; j <= M ; ++ j )
            if ( F[ i ][ j ] > F[ i-1 ][ j ] + T2[ i ] )
                F[ i ][ j ] = F[ i-1 ][ j ] + T2[ i ];
        /* 第三状态 */ 
        for ( int j = 0 ; j <= M ; ++ j )
            if ( F[ i ][ min(j+F2[ i ],M) ] > F[ i-1 ][ j ] + T3[ i ] )
                F[ i ][ min(j+F2[ i ],M) ] = F[ i-1 ][ j ] + T3[ i ];    
    }
    int Min = 0xffffff;
    for ( int i = 0 ; i <= M ; ++ i )
        if ( Min > F[ N ][ i ] )
            Min = F[ N ][ i ];
    return Min;
}

int main()
{
    int T,N,M;
    while ( cin >> T )
    while ( T -- ) {
        cin >> N >> M;
        for ( int i = 1 ; i <= N ; ++ i ) 
            cin >> T1[ i ] >> T2[ i ] >> T3[ i ] >> F1[ i ] >> F2[ i ];
        cout << dp( N, M ) << endl;
    }
    return 0;
}


zoj 2972 - Hurdles of 110m