codevs 3027_线段覆盖 2_dp

发布于 2019-05-19  5 次阅读


题目描述

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


思路

将线段的右端点递增排序,f[i]表示前i条线段最大的价值,数据存在e数组中 f[i]=e[i].w+maxf[j](1<=j<ie[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);
}
]]>