[原创]我的PKU ACM POJ 1020解答

[原创]我的PKU ACM POJ 1020解答

开始用的贪心法，有些数据不能过，后来发现网上说贪心法是不能用于这题的，还有一个反例如下：

1
10 14 1 1 1 1 1 4 4 3 3 3 3 3 3 3

答案是KHOOOOB!

用贪心法是无法解决上面的数据的。

因此，网上参照了DFS搜索弄出了一个AC的代码，基本思路就是从左上开始切，寻找某列已切行数最少的开始，然后从大到小逐个

试蛋糕，看是否能切出来，若当前切割失败，则回溯上一步，换个不同大小的继续试。切完需要的块数就表示刚好可以。

Source Code

Problem: 1020		User: absolute
Memory: 204K		Time: 32MS
Language: C++		Result: Accepted

• Source Code

  #include <stdio.h>
  #include <memory.h>
  int cakeside,piecenum,pieces[11];
  //fillednum stand for the nums had filled
  bool fill(int fillednum,int* used)
  {
      //如果已填的个数等于需求的蛋糕个数则表示刚好
      if(fillednum==piecenum)
          return true;
      int i,j,minusedrow=41,nowcol=0;
      //寻找未填的行数最小的那列
      for(i=1;i<=cakeside;i++)
      {
          if(used[i]<minusedrow)
          {
              minusedrow = used[i];
              nowcol = i;
          }
      }
      //从行数最小的那列开始，从大到小搜索能填入的蛋糕
      for(i=10;i>0;--i)
      {
          if(pieces[i]>0 && i+minusedrow<=cakeside+1 && i+nowcol<=cakeside+1)
          {
              bool flag=true;
              //判断连续的区域是否能放下当前蛋糕
              for(j=nowcol;j<nowcol+i;j++)
              {
                  if(used[j]>minusedrow)
                  {
                      flag=false;
                      break;
                  }
              }
              if(flag)
              {
                  //能放下则更新蛋糕所在的列的已填行数
                  for(j=nowcol;j<nowcol+i;j++)
                      used[j] += i;
                  //当前大小蛋糕数减一
                  pieces[i]--;
                  //继续切下一块蛋糕
                  if(fill(fillednum+1,used))
                      return true;
                  //到这说明上面方案不可行，回溯，不能切当前大小的蛋糕
                  pieces[i]++;
                  for(j=nowcol;j<nowcol+i;j++)
                      used[j] -= i;
              }
          }
      }
      return false;
  }
  int main()
  {
      int ncase,i,j;
      scanf("%d",&ncase);
      while(ncase>0)
      {
          --ncase;
          int sum=0;
          int pieceside;
          scanf("%d %d",&cakeside,&piecenum);
          memset(pieces,0,sizeof(pieces));
          //记录各不同大小的蛋糕个数，大小范围在1-10之间
          for(i=0;i<piecenum;++i)
          {
              scanf("%d",&pieceside);
              //大小为pieceside的个数
              pieces[pieceside]++;
              sum += pieceside*pieceside;
          }
          if(sum!=cakeside*cakeside)
          {
              printf("HUTUTU!\n");
              continue;
          }
          bool IsWaste=true;
          //used[i]记录的是第i列还没填的那行
          int used[41];
          for(i=1;i<=40;i++) used[i]=1;
          //fill表示从第几块蛋糕开始填是否能刚好填满所有蛋糕
          IsWaste = !fill(0,used);
          if(IsWaste)
              printf("HUTUTU!\n");
          else
              printf("KHOOOOB!\n");
  
      }
      return 0;
  }