题意：给出n个小正方形，问能否将这n个小正方形拼成一个边长为s的大正方形（不可重叠，不可留空）(小正方形的边长[1, 10], 1 <= n <= 16)
题目链接：http://poj.org/problem?id=1020
——>>好题，好题，题意是如此的平常，却不容易做……
在小正方形的面积和 == 大正方形的面积的前提下，每次先填最凹的地方，看能否能填完n个小正方形。
#include <cstdio>
#include <cstring>using namespace std;const int maxn = 40 + 10;
const int maxm = 10 + 10;
int s, n, num[maxm], side[maxn];
bool ok;void dfs(int cur)
{if(ok) return;if(cur == n){ok = 1;return;}int min_col = 1, i, j; //找最凹处for(i = 2; i <= s; i++)if(side[i] < side[min_col])min_col = i;int border = s + 1; //最凹处右界for(i = min_col + 1; i <= s; i++)if(side[i] != side[min_col]){border = i;break;}for(i = 10; i >= 1; i--){if(num[i] > 0 && i <= s - side[min_col] && i <= border - min_col){for(j = min_col; j < min_col + i; j++) side[j] += i;num[i]--;dfs(cur + 1);num[i]++;for(j = min_col; j < min_col + i; j++) side[j] -= i;}}
}int main()
{int t, temp, sum, i;scanf("%d", &t);while(t--){sum = 0;memset(num, 0, sizeof(num));memset(side, 0, sizeof(side));scanf("%d%d", &s, &n);for(i = 0; i < n; i++){scanf("%d", &temp);num[temp]++;sum += temp * temp;}ok = 0;if(s * s == sum) dfs(0);if(ok) printf("KHOOOOB!\n");else printf("HUTUTU!\n");}return 0;
}