链接：
http://poj.org/problem?id=2392
代码：
1 #include <map> 2 #include <set> 3 #include <cmath> 4 #include <queue> 5 #include <stack> 6 #include <cstdio> 7 #include <string> 8 #include <vector> 9 #include <cstdlib> 10 #include <cstring> 11 #include <sstream> 12 #include <iostream> 13 #include <algorithm> 14 #include <functional> 15 using namespace std; 16 #define rep(i,a,n) for (int i=a;i<n;i++) 17 #define per(i,a,n) for (int i=n-1;i>=a;i--) 18 #define all(x) (x).begin(),(x).end() 19 #define pb push_back 20 #define mp make_pair 21 #define lson l,m,rt<<1 22 #define rson m+1,r,rt<<1|1 23 typedef long long ll; 24 typedef vector<int> VI; 25 typedef pair<int, int> PII; 26 const ll MOD = 1e9 + 7; 27 const int INF = 0x3f3f3f3f; 28 const int MAXN = 4e4 + 7; 29 // head 30 31 struct Block { 32 int h, a, c; 33 const bool operator<(const Block &t) const { 34 return a < t.a; 35 } 36 }a[410]; 37 38 int dp[MAXN]; 39 int sum[MAXN]; 40 41 int main() { 42 int n; 43 cin >> n; 44 rep(i, 0, n) scanf("%d%d%d", &a[i].h, &a[i].a, &a[i].c); 45 sort(a, a + n); 46 dp[0] = 1; 47 int ans = 0; 48 rep(i, 0, n) { 49 memset(sum, 0, sizeof(sum)); 50 rep(j, a[i].h, a[i].a + 1) if (!dp[j] && dp[j - a[i].h] && sum[j - a[i].h] < a[i].c) { 51 dp[j] = 1; 52 sum[j] = sum[j - a[i].h] + 1; 53 ans = max(ans, j); 54 } 55 } 56 cout << ans << endl; 57 return 0; 58 }