HDU3466-排序+背包

题目地址
转移剩余的空间，当前的剩余的容量为j，则dp[j] 由 dp[j+a[i].p] 转移过来。但是由于物品出现的位置不确定，所以要排个序。不理解要排序的可以用这两组样例试一下：
2 10
1 10 10
2 9 10

2 10
2 9 10
1 10 10

正解为20；
ac代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;
namespace {
  template <typename T> inline void read(T &x) {
    x = 0; T f = 1;char s = getchar();
    for(; !isdigit(s); s = getchar()) if(s == '-') f = -1;
    for(;  isdigit(s); s = getchar()) x = (x << 3) + (x << 1) + (s ^ 48);
    x *= f;
  }
}
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define _for(n,m,i) for (int i = (n); i < (m); i++)
#define _rep(n,m,i) for (int i = (n); i <= (m); i++)
#define lson rt << 1, l, mid
#define rson rt << 1 | 1, mid + 1, r
#define lowbit(x) x & (-x)
#define pii pair<int,int>
#define fi first
#define se second
struct node { 
  int p, q, v;
  bool operator < (const node & a) {
    return q - p > a.q - a.p;
  }
}a[550];      
int dp[5500]; 
int main() {  
  int n, m;   
  while(cin >> n >> m) { 
    memset(dp, 0, sizeof(dp));
    _rep(1,n,i) read(a[i].p), read(a[i].q), read(a[i].v);
    sort(a + 1, a + n + 1);
    _rep(1,n,i) { 
      for(int j = a[i].q - a[i].p; j + a[i].p <= m; j++) { 
        dp[j] = max(dp[j + a[i].p] + a[i].v, dp[j]);
      } 
    } 
    cout << *max_element(dp, dp + m + 1) << endl;  
  } 
}