题目：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 
     
      #include 
      
       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;}