CODEVS 3027线段覆盖2

#include<stdio.h> #include<string.h> #include<stdlib.h> #include <algorithm> #include<iostream> using namespace std; int f[1000000]; //f[i]表示前i个的最大价值（第i个一定取） struct node{ int a,b,c; }x[1010]; int cmp(node x1, node x2){ return x1.b<x2.b; } int n,mx; int main(){ cin>>n; for(int i=1;i<=n;i++) cin>>x[i].a>>x[i].b>>x[i].c; sort(x+1, x+n+1, cmp); for(int i=1;i<=n;i++) {//尝试取第i个区间（一定取） for(int j=0;j<i;j++){//尝试前j个+第i个 if(x[j].b<=x[i].a) f[i]=max(f[i],f[j]+x[i].c); } } for(int i=1;i<=n;i++){ mx=max(mx,f[i]);//找到n个中最大 } cout<<mx; return 0; }