数轴上有n条线段，线段的两端都是整数坐标，坐标范围在0~1000000，每条线段有一个价值，请从n条线段中挑出若干条线段，使得这些线段两两不覆盖（端点可以重合）且线段价值之和最大。
n<=1000
第一行一个整数n，表示有多少条线段。
接下来n行每行三个整数, ai bi ci，分别代表第i条线段的左端点ai，右端点bi（保证左端点<右端点）和价值ci。
输出能够获得的最大价值
3
1 2 1
2 3 2
1 3 4
4
数据范围
对于40%的数据，n≤10；
对于100%的数据，n≤1000；
0<=ai,bi<=1000000
0<=ci<=1000000
//想了很久，dp[i] 意思是 i 起点为 0 为终点为 i 的区间可达最大价值,所以转移方程是 , 具体点，关联到每条边
dp [i] = max ( max ( dp [ 0 --- i - edge[e].len ] ) + edge[e].v , dp [ edge[e].r ] )
所有线段先按右端升序排好序，这样比较有条理，不会乱，再来说上面三个条件的意思
第一个前面的不冲突的最大价值加上这条线段的价值，也就是与这条线段共同覆盖可以达到的价值
第二个是不使用这条线段就有的价值
然后就很简单了。。。不过，若无脑循环 0 --- i - edge[e].len 的话，有点浪费时间，可以用之前的线段的右端点代替，这样就很快了，省时间有些细节要注意。。。
1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4 #include <algorithm>
5 using namespace std;
6
7 struct Edge
8 {
9 int l,r;
10 int v;
11 }edge[1005];
12
13 int dp[1000005];
14
15 int cmp(Edge a,Edge b)
16 {
17 return a.r<b.r;
18 }
19
20 int main()
21 {
22 int n;
23 scanf("%d",&n);
24 for(int i=0;i<n;i++)
25 {
26 int a,b,c;
27 scanf("%d%d%d",&a,&b,&c);
28 edge[i].l=min(a,b);
29 edge[i].r=max(a,b);
30 edge[i].v=c;
31 }
32 sort(edge,edge+n,cmp);
33 for (int i=0;i<n;i++)
34 {
35 for (int j=i-1;j>=0;j--)
36 {
37 if (edge[j].r<=edge[i].l)
38 dp[edge[i].r]=max(dp[edge[j].r]+edge[i].v,dp[edge[i].r]);
39 }
40 dp[edge[i].r]=max(edge[i].v,dp[edge[i].r]);
41 }
42 int ans=0;
43 for (int i=0;i<n;i++)
44 ans=max(ans,dp[edge[i].r]);
45 cout<<ans<<endl;
46 return 0;
47 }
48
49 /*
50 10
51 0 3 4
52 1 4 7
53 15 19 8
54 1 2 6
55 1 3 4
56 2 5 6
57 4 7 7
58 2 4 3
59 3 8 10
60 7 12 2
61 */
原文：http://www.cnblogs.com/haoabcd2010/p/6362650.html