Cake Cutting
Time Limit:1000MS? Memory Limit:65536K
Total Submit:528 Accepted:228

Description

You are given a rectangular cake of integral dimensions w × h. Your goal is to divide this cake into m rectangular pieces of integral dimensions such that the area of the largest piece is minimal. Each cut must be a straight line parallel to one of the sides of the original cake and must divide a piece of cake into two new pieces of positive area. Note that since a cut divides only a single piece, exactly m ? 1 cuts are needed.

If w = 4, h = 4, and m = 4, then the following cuts minimize the area of the largest piece:

However, if w = 4, h = 4, and m = 3, then the following cuts are optimal:

Input

The input test file will contain multiple test cases, each of which consists of three integers w, h, m separated by a single space, with 1 ≤ w, h, m ≤ 20 and m ≤ wh. The end-of-file is marked by a test case with w = h = m = 0 and should not be processed.

Output

For each test case, write a single line with a positive integer indicating the area of the largest piece.

Sample Input

4 4 4
4 4 3
0 0 0

Sample Output

4
6

Source
Stanford Local 2004

用了記憶化搜索, 900多ms才過(guò)掉， rp好啊..

#include? < iostream >
using ? namespace ?std;

int ?f[ 21 ][ 21 ][ 21 ];

int ?lookup( int ?w,? int ?h,? int ?k)
{
???? if ?(f[w][h][k]? > ? 0 )? return ?f[w][h][k];
???? if ?(k? == ? 1 )
???? {
????????f[w][h][k]? = ?w? * ?h;
???????? return ?f[w][h][k];
????}
???? int ?i,?j;
???? int ?max1? = ? 2000000000 ,?max2? = ? 2000000000 ;
???? int ?t;

???? // t?=?0;
???? for ?(i = 1 ;?i < w;?i ++ )
???? {
???????? for ?(j = 1 ;?j < k;?j ++ )
???????? {
???????????? if ?(i * h? >= ?j? && ?(w - i) * h? >= ?k - j)
???????????? {
????????????????t? = ?lookup(i,?h,?j)? > ?lookup(w - i,?h,?k - j)? ? ?lookup(i,?h,?j)?:?lookup(w - i,?h,?k - j);
???????????????? if ?(max1? > ?t)
????????????????????max1? = ?t;
????????????}
????????}
????}

???? // t?=?0;
???? for ?(i = 1 ;?i < h;?i ++ )
???? {
???????? for ?(j = 1 ;?j < k;?j ++ )
???????? {
???????????? if ?(w * i? >= ?j? && ?w * (h - i)? >= ?k - j)
???????????? {
????????????????t? = ?lookup(w,?i,?j)? > ?lookup(w,?h - i,?k - j)? ? ?lookup(w,?i,?j)?:?lookup(w,?h - i,?k - j);
???????????????? if ?(max2? > ?t)
????????????????????max2? = ?t;
????????????}
????????}
????}

????f[w][h][k]? = ?max1? < ?max2? ? ?max1?:?max2;
???? return ?f[w][h][k];
}

int ?g( int ?w,? int ?h,? int ?k)
{
????memset(f,? 0 ,? sizeof (f));
???? return ?lookup(w,?h,?k);
}

int ?main()
{
???? int ?w,?h,?m;

???? while ?(scanf( " %d%d%d " ,? & w,? & h,? & m)? != ?EOF)
???? {
???????? if ?(w? == ? 0 ? && ?h? == ? 0 ? && ?m? == ? 0 )? break ;
????????printf( " %d\n " ,?g(w,?h,?m));
????}
???? return ? 0 ;
}