题目描述

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

思路

将线段的右端点递增排序，f[i]表示前i条线段最大的价值，数据存在e数组中 f[i]=e[i].w+maxf[j](1<=j<i且e[j].l<=e[i].r)

#include 
#include 
#define max(x,y) x>y?x:y
#define maxn 10001
#define INF 0x7f7f7f7f
using namespace std;
int f[maxn];
struct edge
{
    int l,r,w;
}e[maxn];
int cmp(edge a,edge b)
{
    return a.r=1;j--)
            if (e[j].r<=e[i].l) l=max(l,f[j]);
        f[i]+=l;
    }
    int ans=0;
    for (int i=1;i<=n;i++) ans=max(ans,f[i]);
    printf("%d\n",ans);
}