tom的烦恼1ac.cpp

背包类问题浅析和一些背包类问题的解答源程序。

#include <iostream>
using namespace std;

const int N = 30009, TF = 100009;
int n, s[N], t[N], m[N], tt=0, f[TF]={0};

void QSort( int b, int e );    // t <= <= ;   s, t, m

int main(){
    int i, j, k;
    cin >>n;
    for( k=1; k<=n; ++k ){
         cin >>s[k] >>t[k] >>m[k];
         if( t[k] > tt ) tt = t[k];
    }
    QSort( 1, n );
    
    for( i=1; i<=n; ++i ){
         if( (k=f[s[i]]+m[i]) >  f[t[i]] ){
             for( j=t[i]; j<=tt; ++j )
                  f[j] = k;
         }
    }
    
    cout <<f[tt] <<endl;
    return 0;
}

void QSort( int b, int e ){
     static int x, y, z;
     int i = b, j = e;
     x = s[i];   y = t[i];   z = m[i];
     while( i<j ){
            while( (i<j) && (y<=t[j]) ) --j;
            if( i<j ){
                s[i] = s[j];    t[i] = t[j];   m[i] = m[j];
                ++i;
            }
            while( (i<j) && (t[i]<=y) ) ++i;
            if( i<j ){
                s[j] = s[i];    t[j] = t[i];   m[j] = m[i];
                --j;
            }
     }
     s[i] = x;   t[i] = y;   m[i] = z;
     if( b<i-1 ) QSort( b, i-1 );
     if( i+1<e ) QSort( i+1, e );
     return;
}