疯狂的bLue

蔚落 2022-06-14 05:14 202阅读 0赞

#### Problem Description ####

众所周知神秘的 ACM 实验室有一个史诗级的出题狂魔，名曰 bLue。最近 bLue 又露出了邪恶的笑，原来是 bLue 接了为校赛出题的单子。

距离校赛开始还有 N 小时，由于各种奇怪的原因出题组可以出题的时间并不固定，大致可以分为M个时间段。每个时间段可以出的题目数也可能不同。同时由于出题是个煞费心血的事情，所以每个出题时间段结束后，善良的 bLue 会让大家休息 R (1 ≤ R ≤ N ) 小时，以便为接下来的出题事业继续奋斗。

为了能为校赛准备尽可能多的题目以备不时之需，bLue 需要好好地规划好这 N 小时如何安排，当然作为唯一的长者，bLue 一下子就为大家规划好了如何安排出题的时间段。

现在 bLue 想考考你在他完美的安排下出题组最多可以出多少个题目？

#### Input ####

测试数据有多组，输入直到文件结束。

对于每组数据：

*  第一行输入三个数 N (1 ≤ N ≤ 1,000,000), M (1 ≤ M ≤ 1,000), R (1 ≤ R ≤ N)
 *  接下来有 M 行输入，每一行输入三个数 Si (0 ≤ Si < N), Ei (Si < Ei ≤ N) ,Vi (1 ≤ Vi ≤ 1,000,000) (0 < i <= M)，分别表示为第 i 个时间段的开始时间，第 i 段的结束时间，第 i 个时间段可以出的题目数

#### Output ####

对于每组数据，输出出题组最多可以出的题的数目。

#### Example Input ####

15 5 3
    1 4 5
    6 9 4
    3 5 2
    7 10 8
    11 15 2

#### Example Output ####

#### Hint ####

假设出题组在第 5 小时出完了一个时间段的题，他们需要休息 3 小时 (R = 3)，那么他们在第 8 小时又可以继续开始出题了。

#include<stdio.h>
    struct node
    {
        int s;
        int e;
        int v;
    }a[1005];
    int dp[1005];
    int max(int a,int b)
    {
        return (a>b?a:b);
    }
    void qqsort(int left,int right)
    {
        int i=left;
        int j=right;
        struct node mid;
        mid=a[i];
        if(i>=j)
        {
            return ;
        }
        while(i<j)
        {
            while(i<j&&(a[j].e>mid.e||(a[j].e==mid.e&&a[j].s>=mid.s)))
            {
                j--;
            }
            a[i]=a[j];
            while(i<j&&(a[i].e<mid.e||(a[i].e==mid.e&&a[i].s<mid.s)))
            {
                i++;
            }
            a[j]=a[i];
        }
        a[i]=mid;
        qqsort(left,i-1);
        qqsort(i+1,right);
    }
    int main()
    {
        int i,j;
        int n,m,r;
        int max1,max2;
        int ans;
        while(scanf("%d%d%d",&n,&m,&r)!=EOF)
        {
            for(i=1;i<=m;i++)
            {
                scanf("%d%d%d",&a[i].s,&a[i].e,&a[i].v);
            }
            qqsort(1,m);
            ans=0;
            for(i=1;i<=m;i++)
            {
                max2=0;
                for(j=1;j<i;j++)
                {
                    if(a[i].s >= a[j].e+r)
                    {
                        max2=max(dp[j],max2);
                    }
                }
                dp[i]=max2+a[i].v;
                ans=max(dp[i],ans);
            }
            printf("%d\n",ans);
        }
        return 0;
    }