题目：
描述
Nahid Khaleh决定邀请“Shahr-e Ghashang”的孩子参加她的结婚纪念日。她想准备一个已知大小的方形巧克力蛋糕。她要求每个被邀请的人确定他/她想要的那块蛋糕的大小（也应该是方形的）。她知道Kavoosi先生不会浪费任何蛋糕。她想知道她是否可以制作一个这样大小的方形蛋糕，它可以满足所有人的要求，并且没有任何浪费。
输入
输入文件的第一行包含一个整数t（1≤t≤10），测试用例的数量，然后是每个测试用例的输入数据。每个测试用例由一行包含一个整数s，即蛋糕的一侧，后跟一个整数n（1≤n≤16），蛋糕块的数量，后跟n个整数（在1..10范围内） ）指定每件的侧面。
输出
每个测试用例应该有一个输出行，其中包含一个单词KHOOOOB！还是HUTUTU！取决于蛋糕是否可以切成特定尺寸的碎片而没有任何浪费。
样例输入
2
4 8 1 1 1 1 1 3 1 1
5 6 3 3 2 1 1 1
样例输出
KHOOOOB！
HUTUTU！
#include <iostream> using namespace std; int pos[100]; //第i列用了pos[i]行 int cake[18]; //第i种蛋糕的数量 int cake_num; int cake_size; bool DFS(int num) { if (num==cake_num) return true; //蛋糕都用完了返回true int MIN = 999, index = -1; for (int i = 1; i <= cake_size; i++) //找到行数花销最小的列 { if (MIN > pos[i]) { MIN = pos[i]; index = i; } } for (int i = 10; i >= 1; i--) //枚举每一条边 { if (cake[i] && i + MIN <= cake_size&&index + i - 1 <= cake_size) //边界试探 { int flag = 1; for (int j = index; j <= i + index - 1; j++) //枚举后续的列 { if (pos[j] > MIN) //有花销更大的列 那么就不能放在这里 { flag = 0; break; } } if (!flag) continue; cake[i]--; //蛋糕可以放下 for (int j = index; j <= index + i - 1; j++) pos[j] += i; if (DFS(num + 1)) return true; cake[i]++; //放错地方了 for (int j = index; j <= index + i - 1; j++) pos[j] -= i; } } return false; } int main() { int t, edge, sum; cin >> t; while (t--) { sum = 0; memset(pos, 0, sizeof(pos)); memset(cake, 0, sizeof(cake)); cin >> cake_size; cin >> cake_num; for (int i = 1; i <= cake_num; i++) { cin >> edge; cake[edge]++; sum += edge*edge; } if (sum != cake_size*cake_size) { cout << "HUTUTU!" << endl; continue; } if (DFS(0)) cout << "KHOOOOB!" << endl; else cout << "HUTUTU!" << endl; } }
来源：https://www.cnblogs.com/LHJL8023/p/8018114.html
原文：https://www.cnblogs.com/sweet-ginger-candy/p/11518192.html