思路

　　用 f [ i ] [ j ] 来表示第 i 个垃圾被扔下时垃圾堆的高度为 j 时能活下去的时间。

　　一开始考虑在 j 枚举时间，结果T掉了一个点，反而在高度为１～１００的情况下枚举高度更方便。

　　给时间先排序 ( 数据里给出的并不是升序的时间线 ) , 就能保证如果牛能活 ( 注意牛有濒死状态, 也就是 0 血的时候还能秀) 到扔下第 i  + 1 个垃圾时, 如果垃圾高度够了此时耗费的时间是最优的.

　　如果不行的话就让牛一直吃, 找到他最多能活到什么时候.

 

CODE

 

#include  < bits/stdc++.h >
#define  dbg( x ) cout  <<  #x  <<  " = "  << x  << endl
#define  eps  1 e - 8
#define  pi  acos( - 1.0 )

using  namespace std ;
typedef  long  long LL ;

const  int inf  =  0x 3f3f3f3f ;

template < class T > inline  void  read(T  & res )
{
     char c ;T flag = 1 ;
     while((c = getchar()) < ' 0 ' ||c > ' 9 ' )if(c == ' - ' )flag =- 1 ;res =c - ' 0 ' ;
     while((c = getchar()) >= ' 0 ' &&c <= ' 9 ' )res =res * 10 +c - ' 0 ' ;res *=flag ;
}

namespace _buff  {
     const  size_t BUFF  =  1  <<  19 ;
     char  ibuf [BUFF ],  *ib  = ibuf ,  *ie  = ibuf ;
     char  getc()  {
         if  (ib  == ie )  {
            ib  = ibuf ;
            ie  = ibuf  +  fread(ibuf ,  1 , BUFF , stdin );
         }
         return ib  == ie  ?  - 1  :  *ib ++ ;
     }
}

int  qread()  {
     using  namespace _buff ;
     int ret  =  0 ;
     bool pos  =  true ;
     char c  =  getc();
     for  (;  (c  <  ' 0 '  || c  >  ' 9 ' )  && c  !=  ' - ' ; c  =  getc())  {
         assert( ~c );
     }
     if  (c  ==  ' - ' )  {
        pos  =  false ;
        c  =  getc();
     }
     for  (; c  >=  ' 0 '  && c  <=  ' 9 ' ; c  =  getc())  {
        ret  =  (ret  <<  3 )  +  (ret  <<  1 )  +  (c  ^  48 );
     }
     return pos  ? ret  :  -ret ;
}

const  int maxn  =  1007 ;

int d , g ;

struct node {
     int t , f , h ;
}  a [maxn ];

int  f [maxn ][maxn ];

bool  cmp(node  a , node  b )  {
     return  a . t  <  b . t ;
}

int  main()
{
     read(d );read(g );
     for  (  int i  =  1 ; i  <= g ;  ++i  )  {
         read( a [i ]. t );
         read( a [i ]. f );
         read( a [i ]. h );
     }
     sort(a  +  1 , a  + g  +  1 , cmp );
     f [ 0 ][ 0 ]  =  10 ;
     a [ 0 ]  =  { 0 ,  0 ,  0 };
     for  (  int i  =  0 ; i  < g ;  ++i  )  {
         for  (  int j  =  0 ; j  <= d ;  ++j  )  {
             if( f [i ][j ]  >=  a [i  +  1 ]. t )  {
                 int new_high  = j  +  a [i  +  1 ]. h ;
                 if(new_high  >= d )  {
                     printf( " %d \n " , a [i  +  1 ]. t );
                     return  0 ;
                 }
                 f [i  +  1 ][j ]  =  max( f [i  +  1 ][j ],  f [i ][j ]  +  a [i  +  1 ]. f );
                 f [i  +  1 ][new_high ]  =  max( f [i  +  1 ][new_high ],  f [i ][j ]);
             }
         }
     }
     int ans  = INT_MIN ;
     for  (  int i  =  1 ; i  <= g ;  ++i  )  {
        ans  =  max(ans ,  f [i ][ 0 ]);
     }
    cout  << ans  << endl ;
     return  0 ;
}