Codevs3027 线段覆盖二

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

• 思路：如果不是线段而是点，显然这题很容易就能解决。于是我们把每个线段都看成一个点，则记选至第i个线段时的最大价值为f[i]，j为不与i相覆盖的且在i之前的线段（当然，如果要从左往右推的话，这里要事先让线段按右端点排序，因为这样可以使左边尽可能地多使用线段），则有DP方程f[i]=max(f[i],f[j]+seg[i].c)，初始化f[i]=seg[i].c，最后遍历所有f[i]取最大值即可。

• 代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1005;
struct node
{
    int l,r,c;
    node(int l=0,int r=0,int c=0):l(l),r(r),c(c){}
    bool operator <(const node &a) const
    {
        return r<a.r;
    }
};
node seg[maxn];
int f[maxn],n;

void init()
{
    scanf("%d",&n);
    for (int i=1;i<=n;++i)
    {
        int l,r,c;
        scanf("%d%d%d",&l,&r,&c);
        seg[i]=node(l,r,c);
    }
}

void dp()
{
    sort(seg+1,seg+n+1);
    for (int i=1;i<=n;++i)
      f[i]=seg[i].c;
    for (int i=2;i<=n;++i)
      for (int j=1;j<=i-1;++j)
        if (seg[j].r<=seg[i].l)
        {
            f[i]=max(f[i],f[j]+seg[i].c);
        }
    int ans=0;
    for (int i=1;i<=n;++i)
      ans=max(ans,f[i]);
    printf("%d",ans);
}

int main()
{
    init();
    dp();
    return 0;
}