题意简述：将宽为w，高为h的蛋糕分成m块，求所有分法中最大蛋糕面积的最小值。
思路：分解成子问题：min(第一刀竖着切的minmax SS， 第一刀横着切的minmax SH）
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 其中SS = max( S(i, h, k), S(w - i, h, cut?- k - 1) ); （左右半边最大蛋糕最小值的较大值）
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 同理SH = max( S(w, i, k), S(w, h - i, cut?- k - 1) ); （上下半边最大蛋糕最小值的较大值）
?
具体题面：
假设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 时不需要处理，表示输入结束。
输出
每个测试案例的结果占一行，输出一个整数，表示最大蛋糕块的面积下限。
输入样例 1?
4 4 4 4 4 3 0 0 0
输出样例 1
4 6
#include<bits/stdc++.h>
using namespace std;
const int N = 25, INF = 0x3f3f3f3f;
int w, h, m;
int ways[N][N][N * N];
int dfs(int w, int h, int m){
if(w * h < m + 1) return INF; //分不出那么多块
if(m == 0) return w * h; //切好了
if(ways[w][h][m] != -1) return ways[w][h][m]; //记忆
int mincake = INF;
for(int i = 1; i < w; ++ i) //第一刀是竖着切的
for(int k = 0; k < m; ++ k){
int m1 = dfs(i, h, k);
int m2 = dfs(w - i, h, m - k - 1);
mincake = min(mincake, max(m1, m2)); //m1,m2中较大值才是最大蛋糕的最小值
}
for(int i = 1; i < h; ++ i) //第一刀是横着切的
for(int k = 0; k < m; ++ k){
int m1 = dfs(w, i, k);
int m2 = dfs(w, h - i, m - k - 1);
mincake = min(mincake, max(m1, m2));
}
ways[w][h][m] = mincake;
return ways[w][h][m];
}
int main( )
{
while(cin >> w >> h >> m && w != 0){
memset(ways, -1, sizeof ways); //宽为w高为h的蛋糕切m-1刀最大蛋糕面积的最小值
cout << dfs(w, h, m - 1) << endl;
}
return 0;
}
