Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
思路确实很好,根据这个思路写的代码,分享一下(16ms)In Reply To:数据太弱,暴力搜索不剪枝AC! Posted by:boycott at 2008-10-22 22:42:19 #include <stdio.h> #include <memory.h> int square[40]; int side[11]; int size; int ArrangeCake(int remain) { int i, j; int min, minIndex, lasting, width, height; if(!remain) return 1; min = size; lasting = 0; for(i = 0; i < size; i++) { if(square[i] < min) { min = square[i]; minIndex = i; lasting = 1; } if(lasting && square[i] > min) { lasting = 0; width = i - minIndex; } } if(lasting) width = i - minIndex; height = size - min; for(i = width < height ? width : height; i > 0; i--) { if(side[i]) { side[i]--; for(j = 0; j < i; j++) square[minIndex + j] += i; if(ArrangeCake(remain - 1)) return 1; for(j = 0; j < i; j++) square[minIndex + j] -= i; side[i]++; } } return 0; } int main() { int t, n, pieceSize, sum; int i; scanf("%d", &t); while(t--) { memset(side, 0, sizeof(side)); memset(square, 0, sizeof(square)); sum = 0; scanf("%d %d", &size, &n); for(i = 0; i < n; i++) { scanf("%d", &pieceSize); side[pieceSize]++; sum += pieceSize * pieceSize; } if(sum != size * size) printf("HUTUTU!\n"); else { if(ArrangeCake(n)) printf("KHOOOOB!\n"); else printf("HUTUTU!\n"); } } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator