http://acm.hdu.edu.cn/showproblem.php?pid=3466
题意：
最近，iSea去了一个古老的国家。在这么长的时间里，它是世界上最富有和最强大的王国。结果，这个国家的人民仍然非常自豪，即使他们的国家没有那么富有了。
商人是最典型的，每个人只卖一个项目，价格是Pi，但如果你的钱少于Qi，他们会拒绝与你交易，iSea评估每个项目一个值Vi。
如果他有M单位的钱，iSea可以获得的最大价值是多少？
思路：
这道题的话多加了一个Qi。
一定要注意，若要保证动归方程无后效性，dp[j-a[i].p]一定要比dp[j]先算，j最小为a[i].q，所以需按q-p从小到大排序。
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 using namespace std; 5 6 const int maxn = 5000+5; 7 8 int n, m; 9 int dp[maxn]; 10 11 struct node 12 { 13 int p, q, v; 14 }a[maxn]; 15 16 bool cmp(node a, node b) 17 { 18 return a.q-a.p < b.q-b.p; 19 } 20 21 int main() 22 { 23 //freopen("D:\\txt.txt", "r", stdin); 24 while (cin >> n >> m && n && m) 25 { 26 memset(dp, 0, sizeof(dp)); 27 for (int i = 1; i <= n; i++) 28 cin >> a[i].p >> a[i].q >> a[i].v; 29 sort(a + 1, a + 1 + n, cmp); 30 for (int i = 1; i <= n; i++) 31 { 32 for (int j = m; j >= a[i].q; j--) 33 dp[j] = max(dp[j], dp[j - a[i].p] + a[i].v); 34 } 35 cout << dp[m] << endl; 36 } 37 return 0; 38 }