poj 1020 Anniversary Cake

poj 1020 Anniversary Cake

#include <iostream>#include <stdio.h>#include <string.h>using namespace std;int state[41],x,cake[20],s,n,cas,sum;bool ans;void dfs(int dep) {     if (dep==n) {       ans = true;       return;     }     int mini = 100, p;     for (int i=1;i<=s;i++)          if (state[i]<mini) { mini = state[i];         //当前最小的点  p = i;         }     for (int i=10;i>=1;i--) {         if (cake[i]>0 && mini+i-1<=s && p+i-1<=s) {   //以该点为左下，在不超边界的情况下  bool fit = true;    for (int k=p;k<=p+i-1;k++)        if (state[k]>mini) { //如果这一段不是“平的” fit = false;break;        }    if (fit) {       for (int k=p;k<=p+i-1;k++)state[k] += i;       cake[i]--;       dfs(dep+1);       cake[i]++;       for (int k=p;k<=p+i-1;k++)state[k] -= i;    }         }     }}        int main() {    scanf("%d",&cas);    while (cas--) {          scanf("%d%d",&s,&n);          memset(cake,0,sizeof(cake));          sum = 0;          for (int i=1;i<=n;i++) {   scanf("%d",&x);   sum += x*x;   cake[x]++;          }          ans = false;          if (sum==s*s) {  for (int i=1;i<=s;i++) state[i] = 1;  dfs(0);          }          if (ans) printf("KHOOOOB!n");          else printf("HUTUTU!n");    }    return 0;}