学步园

解题思路：

其实这题就是线段覆盖的一个变形，比线段覆盖多了一个所谓的价值，要求使得价值最大，那么只需要在线段覆盖的基础上加一个dp就能过了。

代码：

# include<cstdio>
# include<iostream>
# include<algorithm>

using namespace std;

# define MAX 1234

int dp[MAX];

struct node
{
    int x;
    int y;
    int value;
}a[MAX];

int cmp ( const struct node & xx,const struct node & yy )
{
    return xx.y < yy.y;
}

int main(void)
{
    int n;
    while ( cin>>n )
    {
        for ( int i = 0;i < n;i++ )
        {
            cin>>a[i].x>>a[i].y>>a[i].value;
        }

        sort(a,a+n,cmp);
        
        for ( int i = 0;i < n;i++ )
        {
            dp[i] = a[i].value;
        }

        for ( int i = 0;i < n;i++ )
        {
            for ( int j = 0;j < i;j++ )
            {
                if ( a[i].x >= a[j].y )
                {
                    dp[i] = max( dp[i],dp[j]+a[i].value);
                }
            }
        }

        //printf("%d\n",*max_element(dp,dp+n));

        int _max = dp[0];
        for ( int i = 1;i < n;i++ )
        {
            if ( dp[i] > _max )
            {
                _max = dp[i];
            }
        }
        cout<<_max<<endl;

    }


    return 0;
}