积木城堡.cpp

XC的儿子小XC最喜欢玩的游戏用积木垒漂亮的城堡。城堡是用一些立方体的积木垒成的

#include<stdio.h>
#include <string.h>
int res[100][10001];
int tmp[10001];
int num[100];
int main()
{
 int N,n,nn;
 int mn_num;
 int sum;
 int i=0,j,k,h;
 scanf("%d",&N);
 while(N--)
 {
  scanf("%d",&n);
  i=0;
  h=0;
  memset(res,0,100*10000*sizeof(int));
  mn_num=100000;
  while(n--)
  {
   i=0;
   sum=0;
   while(scanf("%d",&nn))
   { 
    if(nn==-1)
     break;
    num[i++]=nn;
    sum+=nn;
   }
   if(mn_num>sum)
    mn_num=sum;
   for(j=0;j<i;j++)
   {
    for(k=0;k<=sum;k++)
     tmp[k]=res[h][k];
    for(k=0;k<=sum;k++)
     if(tmp[k]&&(k+num[j]<=sum))
     if(!tmp[k+num[j]])
      res[h][k+num[j]] = 1;
    res[h][num[j]] = 1;
   }
   h++;
  }
        int flag ;
  for(j=mn_num;j>=1;j--)
  {
   int flag  = 1;
   if(res[0][j])
   {
    for(k=1;k<h;k++)
    {
     if(!res[k][j])
     {
      flag = 0;
      break;
     }
    }
   }
   else
    flag  = 0;
   if(flag)
    break;
  }
  if(flag)
   printf("%d\n",j);
  else
   printf("0");
 }
 return 0;

}