【Codevs3027】线段覆盖2

problem

solution

codes

//f[i]:到第i条线段为止能获得的最大价值
//f[i]=max{s[i].c,f[j]+s[i].c|j<i&&s[j].b<=s[i].a}
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 1010;
struct seg{ int a, b, c; }s[maxn];
bool cmp(seg a, seg b){ return a.a<b.a; }
int n, f[maxn], ans;
int main(){
    cin>>n;
    for(int i = 1; i <= n; i++)
        cin>>s[i].a>>s[i].b>>s[i].c;
    sort(s+1,s+n+1,cmp);
    for(int i = 1; i <= n; i++){
        f[i] = s[i].c;
        for(int j = 1; j < i; j++)
            if(s[j].b<=s[i].a)f[i] = max(f[i], f[j]+s[i].c);
        ans = max(ans, f[i]);
    }
    cout<<ans<<"\n";
    return 0;
}
  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
 

文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。

原文链接：gwj1314.blog.csdn.net/article/details/80502398