vijos1059 积木城堡(背包)

就是对于每一个城堡，都做一遍能否恰好填充。最后统计n个城堡都有的最大高度。

#include <cstdio> #include <cstring> #define N 105 int n,cnt[10010],mx=0; bool f[10010]; int main(){ // freopen("a.in","r",stdin); scanf("%d",&n); for(int tt=1;tt<=n;++tt){ int a[N],tot=0,sum=0; memset(f,0,sizeof(f));f[0]=1; while(1){ int x; scanf("%d",&x); if(x==-1) break; a[++tot]=x;sum+=x; }if(sum>mx) mx=sum; for(int i=1;i<=tot;++i) for(int j=sum;j>=a[i];--j) if(f[j-a[i]]) f[j]=1; for(int i=0;i<=sum;++i) cnt[i]+=f[i]; } for(int i=mx;i>=0;--i) if(cnt[i]==n){ printf("%d\n",i);return 0; } }