SOJ 2930_积木城堡

【题意】若干个城堡，给定每个城堡的积木数及每块积木的棱长。从城堡中抽出积木使每块城堡高度相同，求最大高度

【分析】城堡的积木选择可以看成01背包问题，从最矮的城堡高度开始依次递减，求出使每个背包都能装满的最大高度。

【代码】

#include<cstdio>

#include<cstring>

#include<cmath>

#include<iostream>

const int INF=0x3fffffff;

const int maxn=110;

int n[maxn];

int h[maxn][maxn];

int v[10100];

using namespace std;

int main (void)

{

    int T,N,a,total,flag,minn,i;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d",&N);

        minn=INF;

        memset(n,0,sizeof(n));

        memset(h,0,sizeof(h));

        for(int k=0;k<N;k++)

        {

            total=0;

            scanf("%d",&a);

            while(a!=-1)

            {

                h[k][n[k]]=a;

                total+=a;

                n[k]++;

                scanf("%d",&a);

            }

            minn=min(total,minn);

        }

        for(i=minn;i>0;i--)

        {

            flag=0;

            for(int j=0;j<N;j++)

            {

                fill(v,v+10100,INF);

                v[0]=0;

                for(int k=0;k<n[j];k++)

                    for(int m=i;m>=h[j][k];m--)

                         v[m]=min(v[m],v[m-h[j][k]]+h[j][k]);

                if(v[i]!=INF)  flag++;

            }

            if(flag==N) break;

        }

        printf("%d\n",i);

    }

        return 0;

}

感觉自己写的好笨，看了白神的代码 感觉有些地方可以优化的=。=（比如对每个城堡积木个数的记录，还有一些细节问题）为了保证原创性，就先不改了，记住就好：）