tom的烦恼3ac.cpp

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

#include <iostream>
using namespace std;

const int N = 30003, M = 100009;
int n, s[N], t[N], v[N];

// 按结束时间从小到大排序
int x, y, z;
void QSort( int b, int e );          // t <= <=

// f[j] 前 j 段时间最优值
// 最优解为 f[t[n]] 
int f[M]={0};
int Dp( void );

int main(){
    int i;
    cin >>n;
    for( i=1; i<=n; ++i )
         cin >>s[i] >>t[i] >>v[i];
    
    srand(time(NULL));
    QSort( 1, n );
    
    cout <<Dp() <<endl;
    
    system( "pause" );
    return 0;
}

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

int Dp( void ){
    int i, j, k, tt=t[n];
    for( i=1; i<=n; ++i ){
         k = f[s[i]] + v[i];
         for( j=t[i]; j<=tt; ++j )
              if( f[j] < k ) f[j] = k;
    }
    return f[tt];
}