切蛋糕 动态规划 noj 1045.txt

包括计算几何、特殊数据结构、组合数学等知识点的代码。每个代码对应一道ACM试题

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <math.h>
using namespace std;

//切蛋糕 动态规划 NOJ 1045
#define MAX 10000
#define NMAX 21
int f[NMAX][NMAX][NMAX];//f[i][j][k]长为i，宽为j，切成k块后的最大面积

void cal()
{
	int i,j,k,m,n,min,max;
	for(i=1;i<NMAX;i++)
		for(j=1;j<NMAX;j++)
			f[i][j][1]=i*j;
	for(i=1;i<NMAX;i++)
	{
		for(j=1;j<NMAX;j++)
		{
			for(k=2;k<NMAX;k++)
			{
				min=MAX;
				for(m=1;m<i;m++)
				{//切一边
					for(n=1;n<=k-1;n++)
					{	//就将i边切成m,i-m两条，其中m条为n块，i-m为k-n块的情况
						//max取切成后的最大面积
						if(f[m][j][n]<f[i-m][j][k-n]) max=f[i-m][j][k-n];		
						else max=f[m][j][n];		
						if(min>max) min=max;//取所有情况中，最大面积的最小面积	
					}					
				}
				for(m=1;m<j;m++)
				{//切另一边
					for(n=1;n<=k-1;n++)
					{	//就将j边切成m,j-m两条，其中m条为n块，j-m为k-n块的情况
						//max取切成后的最大面积
						if(f[i][m][n]<f[i][j-m][k-n]) max=f[i][j-m][k-n];
						else max=f[i][m][n];
						if(min>max) min=max;//取所有情况中，最大面积的最小面积
					}
				}
				f[i][j][k]=min;
			}
		}
	}
}
int main()
{
	int chang,kuang,cut;
	cal();
	scanf("%d%d%d",&chang,&kuang,&cut);
	while(!(chang==0&&kuang==0&&cut==0))
	{
		cout<<f[chang][kuang][cut]<<endl;
		scanf("%d%d%d",&chang,&kuang,&cut);
	}
	return 0;
}