Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 思路确实很好，根据这个思路写的代码，分享一下（16ms）

Posted by Zenomyth at 2009-11-18 13:20:45 on Problem 1020
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: