题目：

思路：贪心对当前能取的，q-p较小的优先考虑

 

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            using namespace std;#define maxn 500005int dp[maxn];struct thing{ int p,q,v;}t[510];bool cmp(thing a,thing b){ return (a.q-a.p)<(b.q-b.p);}int main(){ int n,m; while(scanf("%d%d",&n,&m)!=EOF) { for(int i=1;i<=n;i++) scanf("%d%d%d",&t[i].p,&t[i].q,&t[i].v); sort(t+1,t+n+1,cmp); memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++) for(int j=m;j>=t[i].p;j--) if(j>=t[i].q) dp[j]=max(dp[j],dp[j-t[i].p]+t[i].v); printf("%d\n",dp[m]); } return 0;}