?? 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];
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -