描述
有一块矩形大蛋糕，长和宽分别是整数w 、h。现要将其切成m块小蛋糕，每个小蛋糕都必须是矩形、且长和宽均为整数。切蛋糕时，每次切一块蛋糕，将其分成两个矩形蛋糕。请计算：最后得到的m块小蛋糕中，最大的那块蛋糕的面积下限。
假设w= 4, h= 4, m= 4，则下面的切法可使得其中最大蛋糕块的面积最小。
假设w= 4, h= 4, m= 3，则下面的切法会使得其中最大蛋糕块的面积最小:
输入共有多行，每行表示一个测试案例。每行是三个用空格分开的整数w, h, m ，其中1 ≤ w, h, m ≤ 20 ， m ≤ wh. 当 w = h = m = 0 时不需要处理，表示输入结束。输出每个测试案例的结果占一行，输出一个整数，表示最大蛋糕块的面积下限。样例输入
4 4 4
4 4 3
0 0 0
样例输出
4
6
----------------------------------------------------------------------
[2016年青岛市程序设计竞赛]第四题 当初没时间了，都怪第二题
DP fijk表示把蛋糕i＊j切成k块的最大面积最小
转移把蛋糕分成两块，枚举每块的k
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N=,INF=1e9;
int f[N][N][N],w,h,m;
void solve(){
memset(f,,sizeof(f));
for(int i=;i<=w;i++)
for(int j=;j<=h;j++) f[i][j][]=i*j; for(int i=;i<=w;i++)
for(int j=;j<=h;j++)
for(int k=;k<=min(i*j,m);k++){
f[i][j][k]=INF;
for(int t=;t<i;t++){
//f[i][j][k]=min(f[i][j][k],max(f[t][j][k-1],(i-t)*j));
for(int p=;p<k;p++)
f[i][j][k]=min(f[i][j][k],max(f[t][j][p],f[i-t][j][k-p]));
}
for(int t=;t<j;t++){
//f[i][j][k]=min(f[i][j][k],max(f[i][t][k-1],(j-t)*i));
for(int p=;p<k;p++)
f[i][j][k]=min(f[i][j][k],max(f[i][t][p],f[i][j-t][k-p]));
}
} }
int main(int argc, const char * argv[]) {
while(cin>>w>>h>>m){
if(w==&&h==&&m==) break;
solve();
cout<<f[w][h][m]<<"\n";
} return ;
}