#include <bits/stdc++.h>
using namespace std;
#define MAXN 10001
typedef struct re{
int st ,ed ,value;
}re;
int compare(const void *a , const void *b){
return ((re *)a)->ed - ((re *)b)->ed;
}
re ex[MAXN];
int dp[MAXN];
int main (){
int n;
while (cin>>n){
for (int i = 0 ; i< n ; i++)
scanf("%d%d%d",&ex[i].st,&ex[i].ed,&ex[i].value);
qsort(ex,n,sizeof(re) ,compare);//按照开始日期和结束日期从小到大排序
dp[0] = 0;
dp[1] = ex[0].value;
int maxv = 0;
for (int i = 2 ; i <= n ; i++){
dp[i] = ex[i-1].value;
for (int j = i-1 ; j>=1; --j){
if (ex[j-1].ed<=ex[i-1].st)
dp[i] = max(dp[i] , dp[j]+ex[i-1].value);
}
//cout<<i << " " <<dp[i] <<endl;
maxv = max(maxv,dp[i]);
}
cout<<maxv<<endl;
}
return 0;
}
int compare(const void *a , const void *b){
return ((re *)a)->ed - ((re *)b)->ed;
}
这个函数本来写的
int compare(const void *a , const void *b){
re aa = *(re *)a;
re bb = *(re *)b;
if (aa.st==bb.st)
return aa.ed - bb.ed;
return aa.st - bb.st;
}
超时了，说明细节上的处理很重要
转载请注明原文地址: https://ju.6miu.com/read-1301820.html
