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;

}