链接： http://poj.org/problem?id=2392
需要按每个模块的允许高度升序排序，然后动规求出结果。一开始只是单纯的排序，无法得到最优结果。自己动规的意识还很差。
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> using namespace std; struct Node{ int h, c, a; }arr[405]; bool cmp(Node x, Node y){ if (x.a == y.a){ return x.h > y.h; } return x.a < y.a; } int k; int dp[40050]; int use[40050]; int main(){ scanf("%d",&k); for (int i = 0; i < k; i++){ scanf("%d %d %d", &arr[i].h, &arr[i].a, &arr[i].c); } memset(dp,0,sizeof (dp)); sort(arr,arr+k,cmp); dp[0] = 1; int ans = 0; for (int i = 0; i < k; i++){ memset(use,0,sizeof (use)); for (int j = arr[i].h; j <= arr[i].a; j++){ if (!dp[j] && dp[j - arr[i].h] && use[j - arr[i].h] < arr[i].c ){ use[j] = use[j - arr[i].h] + 1; ans = max(ans,j); dp[j] = 1; } } } printf("%d\n",ans); return 0; }
