Description
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 ( <= K <= ) different types of blocks with which to build the tower. Each block of type i has height h_i ( <= h_i <= ) and is available in quantity c_i ( <= c_i <= ). Due to possible damage caused by cosmic rays, no part of a block of type i can exceed a maximum altitude a_i ( <= a_i <= ). Help the cows build the tallest space elevator possible by stacking blocks on top of each other according to the rules.
Input
* Line : A single integer, K * Lines ..K+: Each line contains three space-separated integers: h_i, a_i, and c_i. Line i+ describes block type i.
Output
* Line : A single integer H, the maximum height of a tower that can be built
Sample Input
Sample Output
Hint
OUTPUT DETAILS: From the bottom: blocks of type , below of type , below of type . Stacking blocks of type and of type is not legal, since the top of the last type block would exceed height .
Source
这道题和 poj 1742 有点类似，只是这道题要先按每个block的最大高度进行排序，这样做的目的是为了获得最优解，想想怎么证明？
然后将dp数组初始化为-1，dp=-1表示取不到，dp[i]>=0表示取到i的时候还能剩下多少个
最后结果就是从最大高度开始寻找dp[i]!=-1的i的值，直接输出即可
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<set>
using namespace std;
#define N 406
#define M 40006
struct Node{
int h,a,c;
}block[N];
int dp[M*N];
bool cmp(Node a,Node b){
return a.a<b.a;
}
int main()
{
int n;
while(scanf("%d",&n)==){
for(int i=;i<n;i++){
scanf("%d%d%d",&block[i].h,&block[i].a,&block[i].c);
}
sort(block,block+n,cmp); memset(dp,-,sizeof(dp));
dp[]=;
for(int i=;i<n;i++){
for(int j=;j<=M;j++){
if(dp[j]>=){
dp[j]=block[i].c;
}
else if(j<block[i].h || dp[j-block[i].h]<=){
dp[j]=-;
}
else if(j>block[i].a){
dp[j]=-;
}
else{
dp[j]=dp[j-block[i].h]-;
}
}
}
for(int i=M;i>=;i--){
if(dp[i]!=-){
printf("%d\n",i);
break;
}
} }
return ;
}