poj1020分蛋糕（用一堆小正方形拼成一个大正方形）

搞了一天了，没搞出来。看了poj上bbs的神代码总算AC了；

基本思路：用一个数组储存每一列（单位为一，range:1 to cakeSize）的“高度”(即row向下延伸的地方)，然后从row最短的地方开始放正方形（从10到1枚举，若放入之后不会超出CakeSize则进行深搜），然后计算能不能放下此正方形。若放不下，continue循环枚举下一个，若可以放下，深搜之，若得，返回true，否则继续枚举下一个方案。

当枚举到最后一个正方形（即正方形的总数）时即符合题意（前提是正方形的总面积加起来等于要求的大正方形的面积），若循环枚举完毕仍不可得，则不能拼成。

AC代码如下：

# include <stdio.h># include <string.h># include <stdlib.h># define DEBUGint s[11];int col[50];int num;int dfs(int cnt) {if(cnt == num) return 1;int min_col = 1;int min_row = col[1];for (int i = 2; i <= s[0]; ++ i) {if(col[i] < col[min_col]) {min_col = i;min_row = col[i];}}for(int x = 10; x > 0; -- x) {if(s[x] && min_col + x - 1 <= s[0] && min_row + x <= s[0]) {int width = 0;for (int i = min_col; col[i] == col[min_col]; ++ i, ++ width);if (width < x) continue;-- s[x];for (int i = 0; i < x; ++ i) {col[i + min_col] += x;}if(dfs(cnt + 1)){return 1;}for (int i = 0; i < x; ++ i) {col[i + min_col] -= x;}++ s[x];}}return 0;}int main () {int t;for (scanf("%d", &t); t; -- t) {memset(s, 0, sizeof(s));memset(col, 0, sizeof(col));scanf ("%d %d", &s[0], &num);for (int i = 0; i < num; ++ i) {int tmp;scanf ("%d", &tmp);++ s[tmp];}int sum = 0;for (int i = 1; i <= 10; ++ i) {sum += s[i] * i * i;}if(sum == s[0] * s[0] && dfs(0)){printf ("KHOOOOB!\n");}else printf ("HUTUTU!\n");}return 0;}

2楼liuquanyi198700昨天 17:18

eqdwke

1楼atupal昨天 03:56

唉，还是太弱阿