Proud Merchants hd 3466

Problem Description Recently, iSea went to an ancient country. For such a long time, it was the most wealthy and powerful kingdom in the world. As a result, the people in this country are still very proud even if their nation hasn’t been so wealthy any more. The merchants were the most typical, each of them only sold exactly one item, the price was Pi, but they would refuse to make a trade with you if your money were less than Qi, and iSea evaluated every item a value Vi. If he had M units of money, what’s the maximum value iSea could get? Input There are several test cases in the input. Each test case begin with two integers N, M (1 ≤ N ≤ 500, 1 ≤ M ≤ 5000), indicating the items’ number and the initial money. Then N lines follow, each line contains three numbers Pi, Qi and Vi (1 ≤ Pi ≤ Qi ≤ 100, 1 ≤ Vi ≤ 1000), their meaning is in the description. The input terminates by end of file marker. Output For each test case, output one integer, indicating maximum value iSea could get. Sample Input 2 10 10 15 10 5 10 5 3 10 5 10 5 3 5 6 2 7 3 Sample Output 5

11

题意：现在你手里有一些钱去买东西，第一行给你的是物品数和你有的钱，接下来的每行中的三个数分别是每个物品的Pi（价格），Qi（如果你剩余的的钱比这个值小酒不能买这个东西，即使你的钱比他的价格高），Vi（这个物品的价值）

思路：首先可以想到是01背包问题，但是刚开始打完代码第二个数据结果是9，后来才发现这个数据要进行sort排序，要用Qi-Pi 然后从大的开始购买，Qi-Pi就是他的相对价值。。。

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; struct node { int Pi; int Qi; int Vi; bool operator < (const node b)const { return Qi-Pi<b.Qi-b.Pi; } }a[5005]; int max(int x,int y) { if(x>y) return x; return y; } int main() { int i,m,n,j,f[5005]; while(~scanf("%d%d",&m,&n)) { memset(f,0,sizeof(f)); for(i=0;i<m;i++) { scanf("%d%d%d",&a[i].Pi,&a[i].Qi,&a[i].Vi); } sort(a,a+m); for(i=0;i<m;i++) { for(j=n;j>=a[i].Qi;j--) { f[j]=max(f[j],f[j-a[i].Pi]+a[i].Vi); } } printf("%d\n",f[n]); } return 0; }