湘潭大学校赛I

Interview Arrangement
Accepted : 58		Submit : 349
Time Limit : 5000 MS		Memory Limit : 65536 KB

作为一名即将毕业大学生，小明即将参加一系列的面试，每场面试都有一个开始时间S_i和一个结束时间T_i。小明可以选择参加面试或者放弃面试，但是迟到和早退是不允许的。每场面试对小明心都有不同的价值V_i。请你帮小明安排一些互不冲突的面试，使得最后参加面试的总价值最大。

Input

有多组测试数据。每组数据的第一行是一个整数1 ≤ N ≤ 100000。接下来N行，每行有三个整数0 ≤ S_i < T_i ≤ 1000000000, -100000 ≤ V_i ≤ 100000.

Output

对每组测试数据，输出最大的总价值。

Sample Input

3

1 2 1

2 3 1

3 4 1

3

1 3 1

2 4 1

3 5 1

Sample Output

3

2

#include"stdio.h"
#include"stdlib.h"

struct node
{
    __int64 a,b;
    __int64 v;
    __int64 sum;
    int forward,num;
}count[100005],count1[100005];

int cmp(const void *a,const void *b)
{
    node *aa=(node*)a,*bb=(node*)b;
    if(aa->b!=bb->b)
        return aa->b>bb->b?1:-1;
    else
        return aa->a>bb->a?1:-1;
}

int cmp1(const void *a,const void *b)
{
    node *aa=(node*)a,*bb=(node*)b;
    if(aa->a!=bb->a)
        return aa->a>bb->a?1:-1;
    else
        return aa->b>bb->a?1:-1;
}



int main( )
{
    int n,i,cnt;
    __int64 x;
    while(~scanf("%d",&n))
    {
        cnt=0;
        for(i=0;i<n;i++)
        {
            scanf("%I64d%I64d%I64d",&count[i].a,&count[i].b,&count[i].v);
            count[i].sum=count1[i].sum=0;//sum表示到此处所获得的价值最大是多少；
        }
        qsort(count,n,sizeof(node),cmp);//对原数据按结束时间排序；
        for(i=0;i<n;i++)
        {
            count1[i].a=count[i].a;count1[i].b=count[i].b;
            count[i].num=count1[i].num=i;//num表示按结束时间排序后所获得的相对顺序；
        }
        qsort(count1,n,sizeof(node),cmp1);//相对于开始时间排序；
        for(i=0;i<n;i++)                //本代码的纠结之处，通过相对顺序找出每个任务之前的那一个任务的序号，用forward表示；
        {
            if(count[i].b>count1[cnt].a)
            {
                count[count1[cnt].num].forward=i-1;
                cnt++;
                i--;
            }
            if(cnt==n)
                break;
        }
        for(i=0;i<n;i++)    //这里挺容易理解的dp找出每个任务结束后的最大价值；
        {
            if(count[count[i].forward].sum<0)
                x=0;
            else
                x=count[count[i].forward].sum;
            if(x+count[i].v>count[i-1].sum)
                count[i].sum=count[i].v+x;
            else
                count[i].sum=count[i-1].sum;
        }
        printf("%I64d\n",count[n-1].sum);
    }
    return 0;
}