学步园

思路：

       看大牛的解题报告，需要对q-p排序（从大到小）；

       注意：qsort()函数要用c++编译，用c会报错；

       AC代码：

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
struct node
{
   int c;
   int s;
   int w;
}a[505];
int dp[5005];
int V;
int cmp(const void *a,const void *b)
{
   struct node *x=(node *)a;
   struct node *y=(node *)b;
   return (x->s-x->c)>(y->s-y->c)?1:-1;
}
void ZeroOnePack(int c,int s,int w)
{
     int v;
	 for(v=V;v>=s;v--)
		   if(dp[v]<dp[v-c]+w)
		        dp[v]=dp[v-c]+w;
}
int main()
{
    int n;
	int i;
	while(scanf("%d%d",&n,&V)!=-1)
	{
	     for(i=1;i<=n;i++)
			 scanf("%d%d%d",&a[i].c,&a[i].s,&a[i].w);
         qsort(a+1,n,sizeof(a[1]),cmp);
		 memset(dp,0,sizeof(dp));
		 for(i=1;i<=n;i++)
			 ZeroOnePack(a[i].c,a[i].s,a[i].w);
		 printf("%d\n",dp[V]);
	}
	return 0;
}