| ||||||||||
| 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