vijos1059-背包計數-積木城堡

用不同的正方體積木建造 n個城堡。

要求建造的時候 下面的比上面的大。

為了讓 n個城堡一樣高，可以拿走他們中的積木。

問你最大高度多少

城堡累放的規則，沒有什麼意義啊qwq

用01背包 統計 出現每個城堡的高度的出現次數，

然後 從大到小 統計哪個 高度在n個城堡均出現。

這樣比較麻煩一點，用的空間也比較大。

可以 用&操作，這樣隻保留 一個一維數組就行，豈不美哉。

#include <bits/stdc++.h>
using namespace std;
const int maxn=;
int dp[maxn][];
int num[maxn];
int all[maxn];
int a[maxn][maxn];
int main()
{   int t,s,a1;
    scanf("%d",&t);
   int all_sum=;
    for(int i=;i<t;i++){
        s=;
        int sum=;
        while(){
            scanf("%d",&a1);
            if(a1==-)break;
            a[i][s++]=a1;
            sum+=a1;
        }
        num[i]=s;
        all[i]=sum;
        all_sum=min(all[i],all_sum);
    }
    for(int i=;i<t;i++){
            dp[i][]=;
        for(int j=;j<num[i];j++){
            for(int x=all[i];x>=a[i][j];x--)
                dp[i][x]+=dp[i][x-a[i][j]];//統計數目
        }
    }
    //cout<<all_sum<<endl;
    int ss=;
    bool flag;
    /*for(int i=0;i<t;i++){
        for(int j=0;j<=5;j++){
            printf("%d ",dp[i][j]);
        }
        cout<<endl;

    }*/
    for(int i=all_sum;i>=;i--){
        flag=false;
        for(int j=;j<t;j++){
            if(dp[j][i]==)
            {flag=true;
            break;}
        }
        if(!flag)
        {ss=i;break;}
    }
    printf("%d\n",ss);
    return ;
}