题目来源：http://poj.org/problem?id=1020
题目大意：有一块边长为s的正方形大蛋糕，有n个客人，每个客人想分一块边长为si的正方形蛋糕。求这块大蛋糕能否恰好满足所有客人的需求而不浪费。
输入：第一行为测试用例数。接下来每行的第一个数位大蛋糕的边长，第二个数位客人的数目n，接下来的n个数为每个客人想要的蛋糕的边长。
输出：若能恰好分完输出“KHOOOOB!”，否则输出“HUTUTU!”
Sample Input
2
4 8 1 1 1 1 1 3 1 1
5 6 3 3 2 1 1 1
Sample Output
KHOOOOB!
HUTUTU!
一开始用贪心方法做，即从大块的开始切，总是选最靠近左下角的位置开始切。大多数用例都可以通过，直到遇到这组数据：
10 14 1 1 1 1 1 4 4 3 3 3 3 3 3 3
发现贪心是有问题的。
后来看了牛人的思路，用DFS解决。
切蛋糕时总是自下而上，自左而右。优先切大蛋糕。
解决方案精彩的地方不在于DFS本身，而在于每切一次蛋糕，标记所有蛋糕位置的方法。标记每个格子的状态再查找会TLE。牛人想到的方法是把蛋糕“按列标记”。建立一维数组，d[s],s为大蛋糕边长，d[i]记录每列第一个为空的格子的行号。
//////////////////////////////////////////////////////////////////////////
// POJ1020 Anniversary Cake
// Memory: 268K Time: 485MS
// Language: C++ Result: Accepted
//////////////////////////////////////////////////////////////////////////
#include <iostream>
using namespace std; int s, n;
int c[];
int d[]; int sum;
bool ok; void reset() {
memset(c, , sizeof(c));
for (int i = ; i < ; ++i) {
d[i] = ;
}
sum = ;
ok = false;
} void dfs(int a) {
if (a == n) {
ok = true;
exit;
}
int i, j;
int row, clo;
bool f;
for (i = , clo = ; i <= s; ++i) {
if (d[i] < clo) {
clo = d[i];
row = i;
}
}
for (i = ; i > ; --i) {
if (c[i] > && row + i - <= s && clo + i - <= s) {
for (j = row, f = true; j <= row + i - ; ++j) {
if (d[j] > clo) {
f = false;
break;
}
}
if (f) {
for (j = row; j <= row + i - ; ++j) {
d[j] += i;
}
--c[i];
dfs(a + );
++c[i];
for (j = row; j <= row + i - ; ++j) {
d[j] -= i;
}
}
}
}
} int main(void) {
int nCase;
cin >> nCase;
for (int caseNo = ; caseNo <= nCase; ++caseNo) {
reset();
cin >> s >> n;
for (int i = ; i <= n; ++i) {
int t ;
cin >> t;
++c[t];
sum += t * t;
}
if (sum != s * s) {
cout << "HUTUTU!" << endl;
continue;
}
dfs();
if (ok) {
cout << "KHOOOOB!" <<endl;
}
else {
cout << "HUTUTU!" << endl;
}
}
system("pause");
return ;
}