多重背包 POJ - 2392 

妖狐艹你老母 2022-06-17 09:23 185阅读 0赞

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  
  
  
\* Line 1: A single integer, K  
  
\* Lines 2..K+1: Each line contains three space-separated integers: h\_i, a\_i, and c\_i. Line i+1 describes block type i.  
  
Output  
  
  
\* Line 1: A single integer H, the maximum height of a tower that can be built  
  
Sample Input  
  
3  
7 40 3  
5 23 8  
2 52 6  
  
Sample Output  
  
48  
  
Hint  
  
  
OUTPUT DETAILS:  
  
From the bottom: 3 blocks of type 2, below 3 of type 1, below 6 of type 3. Stacking 4 blocks of type 2 and 3 of type 1 is not legal, since the top of the last type 1 block would exceed height 40.

#include <iostream>
    #include <cstring>
    #include <cstdio>
    #include <string>
    #include <map>
    #include <queue>
    #include <set>
    #include <algorithm>
    #define LL long long
    #define INF 0x7fffffff
    #define MAX 200010
    using namespace std;
    struct node
    {
        int h,maxx,c;
    } a[450];
    bool cmp(node x,node y)
    {
        return x.maxx<y.maxx;
    }
    int dp[400000];
    int sum[400000]; //数组里是统计的石块的个数  但下标表示的是垒的石头的高度  所以sum数组的大小为所有石头的最高高度和40万
    int n;
    int main()
    {
        while(scanf("%d",&n)!=EOF)
        {
            int ans=0;
            for(int i=1; i<=n; i++)
                scanf("%d%d%d",&a[i].h,&a[i].maxx,&a[i].c);
            sort(a+1,a+1+n,cmp);
    
            memset(dp,0,sizeof(dp));
            dp[0]=1;
            for(int i=1; i<=n; i++)
            {
                memset(sum,0,sizeof(sum));
                for(int j=a[i].h; j<=a[i].maxx; j++)
                {
                    if( !dp[j] && dp[j-a[i].h] && sum[j-a[i].h]<a[i].c )  //如果这块石头没被垒过 && 这个石头可以继续放上 && 这个石头的数量小于他的数量限制
                    {
                        dp[j]=1;
                        sum[j]=sum[j-a[i].h]+1;  //这种类型的石块数量加1
                        if(ans<j) ans=j;
                    }
                }
    
            }
    
            printf("%d\n",ans);
        }
        return 0;
    
    }
    
    
    /*题意：
    一群牛要上太空，给出n种石块，每种石块给出单块高度，总高度不能超过的最大值，数量。
    要求用这些石块能组成的最大高度*/
    
    /*
    思路：
    在进行多重背包之前要进行一次排序，将最大高度小的放在前面，
    只有这样才能得到最优解，如果小的放在后面的话，那么最高高度就被整体拉低了
    排序之后就可以进行完全背包了*/