1932.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1932 on 2006-07-01 at 15:41:13 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 21;
const int INF = 1 << 28;

int area[N][N][N];

int cut(int, int, int);

int main()
{
	int w, h, m;

	memset(area, 0, sizeof(area));
	while(scanf("%d %d %d", &w, &h, &m) != EOF && w != 0)
		printf("%d\n", cut(w, h, m-1));
	
	return 0;
}

int cut(int w, int h, int m)
{
	if(w < h) swap(w, h);
	int &v = area[w][h][m], i, j;
	if(v != 0) return v;
	else if(w*h <= m+1) v = 1;
	else if(m == 0) v = w*h;
	else {
		v = INF;
		for(i = 0; i < m; i++) {
			for(j = 1; j < w; j++) v = min(v, max(cut(j, h, i), cut(w-j, h, m-1-i)));
			for(j = 1; j < h; j++) v = min(v, max(cut(w, j, i), cut(w, h-j, m-1-i)));
		}
	}
	return v;
}