题意:

给定$n$种积木，每种积木都有一个高度$h[i]$，一个数量$num[i]$，还有一个限制条件，这个积木所在的位置不能高于$limit[i]$,问能叠起的最大高度

解题思路

这个问题类似于经典的“背包问题”，但有一些额外的限制。我们需要选择一定数量的每种块，使得在堆叠时，每个块的顶部高度（即该块及其下方所有块的高度之和）不超过该块的$a_i$。目标是最大化总高度$H$。

1、关键点： 块的顺序：块的堆叠顺序会影响是否满足$a_i$的限制。直观上，应该先放$a_i$较小的块，因为这样它们可以放在较低的位置，避免超过其$a_i$限制。

例如，如果一个块的$a_i$很小，那么它应该尽可能放在底部，这样它的顶部高度不会超过$a_i$。

因此，首先需要将所有块按照$a_i$从小到大排序。

2、动态规划：类似于无限背包问题，但每种块的数量是有限的（多重背包问题）。

定义$dp[j]$为是否可以构建高度为j的塔，并且在构建时满足所有块的限制。

初始化：$dp[0] = True$（高度为$0$总是可以构建）。

对于每种块$i$，按照排序后的顺序，考虑使用$0$到$c_i$个该块，更新$dp$数组。

在更新时，需要确保新增的块不会违反其$a_i$限制。即，如果当前已经堆叠了高度为$j$的塔，新增一个块$i$后，新的高度为$j + h_i$，必须满足 $j + h_i ≤ a_i$。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=40000+5;
 
int n;//木块种类
struct Node//每种木块
{
    int high,num,limit;
    bool operator<(const Node &rhs)const
    {
        return limit<rhs.limit;
    }
}nodes[400+5];
int dp[maxn];
 
//一次01背包过程
void ZERO_ONE_PACK(int cost,int limit)
{
    for(int i=limit;i>=cost;i--)
        dp[i] = max(dp[i], dp[i-cost]+cost);
}
 
//一次完全背包过程
void COMPLETE_PACK(int cost,int limit)
{
    for(int i=cost;i<=limit;i++)
        dp[i] = max(dp[i], dp[i-cost]+cost);
}
 
//一次多重背包过程
void MULTIPLY_PACK(int cost,int limit,int num)
{
    if(cost*num>=limit)
    {
        COMPLETE_PACK(cost,limit);
        return ;
    }
 
    int k=1;
    while(k<num)
    {
        ZERO_ONE_PACK(cost*k,limit);
        num-=k;
        k*=2;
    }
    ZERO_ONE_PACK(cost*num,limit);
}
 
int main()
{
    while(scanf("%d",&n)==1)
    {
        //读取输入+排序
        for(int i=1;i<=n;i++)
            scanf("%d%d%d",&nodes[i].high,&nodes[i].limit,&nodes[i].num);
        sort(nodes+1,nodes+n+1);
 
        //初始化dp+递推
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;i++)
            MULTIPLY_PACK(nodes[i].high, nodes[i].limit, nodes[i].num);
 
        //统计结果输出
        int ans=0;
        for(int i=0;i<=nodes[n].limit;i++)
            ans=max(ans,dp[i]);
        printf("%d\n",ans);
    }
    return 0;
}