学步园

思路：多重背包。 只是有一点小变形 把block按它的的ai从小到大排序，从小的开始搭建 因为如果从大的开始，就有可能把小的给忽略掉
用dp[] 记录状态 能否达到这个高度 然后在每次比较时 选出当前能达到的最大高度

//332K   
172MS
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define Max 40010
#define M 450
using namespace std;
int ans;
int dp[Max];
struct data
{
    int
h,a,c;
}node[M];

int max (int a, int b)
{
    return a
> b ? a : b;
}
bool cmp (data a,data b)
{
    return a.a
< b.a;
}
void MulPack(int cost,int amount,int cap)
{
    int i;
    if
(cost*amount >= cap)
    {
       
for (i = cost;i <= cap;i ++)
           
if (dp[i - cost])
           
{
               
dp[i] = 1;
               
ans = max
(ans,i);     
//每次选择当前能达到的最大高度，下面的也一样
           
}
       
return ;
    }
    int k =
1;
    while (k
< amount)
    {
       
for (i = cap;i >= k*cost;i --)
           
if (dp[i - k*cost])
           
{
               
dp[i] = 1;
               
ans = max (ans,i);
           
}
       
amount -= k;
       
k *= 2;
    }
    for (i =
cap;i >= amount*cost;i --)
       
if (dp[i - amount*cost])
       
{
           
dp[i] = 1;
           
ans = max(ans,i);
       
}