题解 P1504 【积木城堡】

Dispwnl · 2017-10-22 17:32:10 · 题解

求出最大高度

从最大高度~1枚举

如果能恰好达到这个高度（即用它有的积木恰好能拼出）有n个城堡

就输出这个高度

每输入一组数据

一遍01背包，拼出一个高度，这个高度城堡个数++

都没有就输出0

# include<iostream>
# include<cstring>
using namespace std;
int n,maxn,x,g,sum;
int a[1001],ans[100001];
bool f[100001];
int main()
{
    cin>>n;
    for(int k=1;k<=n;k++)
      {
          memset(f,0,sizeof(f));
        int g=0,sum=0;
          while(1)
          {
              cin>>x;
              if(x<0) break;
              a[++g]=x;
              sum+=x;
        }
        f[0]=1;
        a[0]=g;
        if(sum>maxn) maxn=sum;
        for(int i=1;i<=g;i++)
          {
              for(int j=sum;j>=a[i];j--)
              if(f[j-a[i]]&&!f[j])
              f[j]=1,ans[j]++;
          }
      }
    for(int i=maxn;i>=0;i--)
      {
        if(ans[i]==n)
        {
            cout<<i;
            return 0;
        }
      }
    cout<<0;
    return 0;
}