The cows are going to space! They plan to achieve orbit by building a sort of space elevator: a giant tower of blocks. They have K (1 <= K <= 400) different types of blocks with which to build the tower. Each block of type i has height h_i (1 <= h_i <= 100) and is available in quantity c_i (1 <= c_i <= 10). Due to possible damage caused by cosmic rays, no part of a block of type i can exceed a maximum altitude a_i (1 <= a_i <= 40000).
Help the cows build the tallest space elevator possible by stacking blocks on top of each other according to the rules.
Input
Output
Sample Input
3 7 40 3 5 23 8 2 52 6
Sample Output
48
Hint
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<queue> #include<stack> #include<map> #include<set> #include<vector> #include<cmath> const int maxn=4e4+5; typedef long long ll; using namespace std; struct node { int h,a,c; }p[maxn]; int dp[maxn]; bool cmp(node x,node y) { return x.a<y.a; } int main() { int K; cin>>K; for(int t=1;t<=K;t++) { scanf("%d%d%d",&p[t].h,&p[t].a,&p[t].c); } sort(p+1,p+K+1,cmp); for(int t=1;t<=K;t++) { for(int j=1;j<=p[t].c;j++) { for(int k=p[t].a;k>=p[t].h;k--) { dp[k]=max(dp[k],dp[k-p[t].h]+p[t].h); } } } int ans=0; for(int t=0;t<=p[K].a;t++) { ans=max(ans,dp[t]); } printf("%d\n",ans); return 0; }
原文：https://www.cnblogs.com/Staceyacm/p/10821676.html