?? 切蛋糕 動態規劃 noj 1045.txt
字號:
#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;
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -