3027 线段覆盖 2

 

 时间限制: 1 s

 空间限制: 128000 KB

 题目等级 : 黄金 Gold

 

 

题目描述 

Description

数轴上有n条线段，线段的两端都是整数坐标，坐标范围在0~1000000，每条线段有一个价值，请从n条线段中挑出若干条线段，使得这些线段两两不覆盖（端点可以重合）且线段价值之和最大。

n<=1000

输入描述 

Input Description

第一行一个整数n，表示有多少条线段。

接下来n行每行三个整数, ai bi ci，分别代表第i条线段的左端点ai，右端点bi（保证左端点<右端点）和价值ci。

输出描述 

Output Description

输出能够获得的最大价值

样例输入 

Sample Input

3

1 2 1

2 3 2

1 3 4

样例输出 

Sample Output

4

数据范围及提示 

Data Size & Hint

数据范围

对于40%的数据，n≤10；

对于100%的数据，n≤1000；

0<=ai,bi<=1000000

0<=ci<=1000000

f[i] = 表示选了i条线段时的最大价值。

先按右端点排序，如果两条线段不重合，有选与不选两种选择，取打。

f[i] 是当选了i条线段时的最大价值，不意味着f[n]就是答案，因为有可能选少于n条的线段时价值最大。

1 #include
          
            2 #include
           
             3 using namespace std; 4 struct Set{ 5     int l,r,w; 6     bool operator < (const Set &a) const  7     { 8         return r < a.r; 9     }10 }s[1010];11 int f[1010];12 int n,ans;13 int main()14 {15     scanf("%d",&n);16     for (int i=1; i<=n; ++i)17         scanf("%d%d%d",&s[i].l,&s[i].r,&s[i].w);18     sort(s+1,s+n+1);19     for (int i=0; i<=n; ++i)20         for (int j=0; j<=i; ++j)21             if (s[i].l>=s[j].r) f[i] = max(f[i],s[i].w+f[j]);22     for (int i=1; i<=n; ++i)23         ans = max(ans,f[i]);24     printf("%d",ans);25     return 0;26 }#include
            
             27 #include
             
              28 using namespace std;29 struct Set{30     int l,r,w;31     bool operator < (const Set &a) const 32     {33         return r < a.r;34     }35 }s[1010];36 int f[1010];37 int n,ans;38 int main()39 {40     scanf("%d",&n);41     for (int i=1; i<=n; ++i)42         scanf("%d%d%d",&s[i].l,&s[i].r,&s[i].w);43     sort(s+1,s+n+1);44     for (int i=0; i<=n; ++i)45         for (int j=0; j<=i; ++j)46             if (s[i].l>=s[j].r) f[i] = max(f[i],s[i].w+f[j]);47     for (int i=1; i<=n; ++i)48         ans = max(ans,f[i]);49     printf("%d",ans);50     return 0;51 }