Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  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:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator