?? tom的煩惱4ac.cpp
字號(hào):
#include <iostream>
using namespace std;
const int N = 30003, M = 100009;
int n, s[N], t[N], v[N];
// 按結(jié)束時(shí)間從小到大排序
int x, y, z;
void QSort( int b, int e ); // t <= <=
// 求前 time 時(shí)間,前 j 個(gè)零件最優(yōu)值
// 最優(yōu)解為 f[t[n]]
const int OO = 2123456789;
int f[M];
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 time=1, j=1;
t[n+1] = OO;
f[0] = 0;
while( time<=t[n] ){
while( time < t[j] ){
f[time] = f[time-1];
++time;
}
f[time] = f[time-1];
while( time == t[j] ){
if( f[time] < f[s[j]] + v[j] ) f[time] = f[s[j]] + v[j];
++j;
}
++time;
}
return f[t[n]];
}
?? 快捷鍵說(shuō)明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號(hào)
Ctrl + =
減小字號(hào)
Ctrl + -