3063235_ac_46ms_184k.c

来自「北大大牛代码 1240道题的原代码 超级权威」· C语言 代码 · 共 62 行

#include <stdio.h>
#include <string.h>

int dp[21][21][21];

int cut(int w,int h,int k)
{
	int i, j;
	int max1, max2;
	int t1, t2;

	if(dp[w][h][k]>0)
		return dp[w][h][k];
	if(k==1)
	{
		dp[w][h][k] = w*h;
		return dp[w][h][k];
	}
	max1 = max2 = 2100000000;
	for(i = 1; i < w; i++)
	{
		for(j = 1; j < k; j++)
		{
			if(i*h>=j&&(w-i)*h>=k-j)
			{
				t1 = cut(i,h,j);
				t2 = cut(w-i,h,k-j);
				t1 = t1>t2?t1:t2;
				max1 = max1<t1?max1:t1;
			}
		}
	}
	for(i = 1; i < h; i++)
	{
		for(j = 1; j < k; j++)
		{
			if(i*w>=j&&(h-i)*w>=k-j)
			{
				t1 = cut(w,i,j);
				t2 = cut(w,h-i,k-j);
				t1 = t1>t2?t1:t2;
				max2 = max2<t1?max2:t1;
			}
		}
	}
	dp[w][h][k] = max1<max2?max1:max2;
	return dp[w][h][k];
}
int main()
{
	int w, h, k;

	memset(dp,0,sizeof(dp));
	while (scanf("%d%d%d",&w,&h,&k)==3)
	{
		if(!w&&!h&&!k)
			break;
		else
			printf("%d\n",cut(w,h,k));
	}
	return 0;
}