【codevs3012】线段覆盖4

#include<algorithm>
#include<iostream>
#include<cstdio>
using namespace std;
int n;
long long ans[1000010];//ans[i]表示i以前所有线段经过选择的答案，因为i以前都选好，所以无后效性，可以进行dp 
struct in
{
    int l,r,c;
}ter[1000010];
bool cmp(in a,in b)
{
    return a.r<b.r;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d%d",&ter[i].l,&ter[i].r,&ter[i].c);
        if(ter[i].l>ter[i].r)
            swap(ter[i].l,ter[i].r);//防止l大于r 
    }
    sort(ter+1,ter+1+n,cmp);//提前按照右端点的大小排序 
    int pos=0,i=1;
    for(pos=1;i<=n;pos++)//pos是枚举的位置，i是枚举的哪条线段 
    {
        ans[pos]=ans[pos-1];//假设没有选以pos为右端点的情况 
        while(ter[i].r==pos&&i<=n)
            ans[pos]=max(ans[pos],ans[ter[i].l]+ter[i].c),i++;
    }
    printf("%lld",ans[pos-1]);//多加出去的要减回来 
}