题目描述 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
分类标签 Tags 点此展开
思路：记选至第i个线段时的最大价值为f[i]，j为不与i相覆盖的且在i之前的线段（当然，如果要从左往右推的话，这里要事先让线段按右端点排序，因为这样可以使左边尽可能地多使用线段），则有DP方程f[i]=max(f[i],f[j]+seg[i].c)，初始化f[i]=seg[i].c，最后遍历所有f[i]取最大值即可。（要注意因为f[j]已经被前面的边更新过了，所以此时f[j]代表的可能不止一条边，所以对于f[i]，只有一个f[j]更新成功就可以了）。
代码：
#include< cstdio >
#include<
algorithm >
#include<
iostream >
using namespace
std;
const int
INFn=1001;
long long int
f[INFn];
int n;
struct
Edge{
int x,y;
long long int
w;
};
Edge
edge[INFn];
int cmp(const
struct Edge &a,const struct Edge &b)
{
return a.y
}
void
input()
{
scanf("%d",&n);
for(int
i=1;i<=n;++i)
{
scanf("%d%d%d",&edge[i].x,&edge[i].y,&edge[i].w);
}
sort(edge+1,edge+n+1,cmp);
}
void dp()
{
for(int
i=1;i<=n;++i)
f[i]=edge[i].w;//对于没有边可以与之衔接的边，就赋值为它自身的价值
for(int
i=2;i<=n;++i)
}
int main()
{
input();
dp();
long long int
maxx=-1;
for(int
i=1;i<=n;++i)
if(f[i]>maxx)
maxx=f[i];
cout<<maxx<<endl;
return 0;
}