青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

隨筆 - 87  文章 - 279  trackbacks - 0
<2025年9月>
31123456
78910111213
14151617181920
21222324252627
2829301234
567891011

潛心看書研究!

常用鏈接

留言簿(19)

隨筆分類(81)

文章分類(89)

相冊

ACM OJ

My friends

搜索

  •  

積分與排名

  • 積分 - 219402
  • 排名 - 118

最新評論

閱讀排行榜

評論排行榜

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 mwh. 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才過掉, 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 ;
}
posted on 2006-09-07 23:43 閱讀(586) 評論(0)  編輯 收藏 引用 所屬分類: ACM題目
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            亚洲高清av| 国产精品福利av| 国产午夜精品久久久| 午夜老司机精品| 亚洲综合好骚| 国内精品国产成人| 欧美电影免费观看高清| 免费日韩av| 亚洲视屏在线播放| 亚洲一区二区三区四区五区黄 | 亚洲二区视频在线| 久久久久久久久久久久久9999 | 国产日韩欧美一二三区| 久久久久久久尹人综合网亚洲 | 一区二区三区国产精品| 国产精品一卡二| 欧美91福利在线观看| 欧美激情免费观看| 欧美亚洲免费电影| 久色成人在线| 亚洲尤物视频在线| 欧美一区二区高清| 日韩视频永久免费| 亚洲午夜国产成人av电影男同| 国产一区二区三区精品久久久| 欧美激情一区二区在线| 国产精品视频免费观看www| 久久综合国产精品| 欧美三区在线视频| 免费看黄裸体一级大秀欧美| 欧美日韩中文字幕精品| 美女视频黄a大片欧美| 国产精品99免费看 | 久久中文字幕一区| 欧美天天综合网| 欧美激情久久久久久| 国产伦精品一区二区三区视频黑人 | 久久―日本道色综合久久| 欧美美女视频| 狂野欧美一区| 国产精品一区视频网站| 亚洲激情啪啪| 亚洲成人在线| 欧美一区二区三区四区视频| 亚洲午夜在线观看| 欧美成人亚洲成人日韩成人| 久久久久一区二区| 国产精品欧美久久| 亚洲精品无人区| 亚洲精品久久视频| 久久一区欧美| 久久综合成人精品亚洲另类欧美| 国产精品久久久久久久午夜| 日韩一区二区精品在线观看| 亚洲精品国产精品国自产在线| 久久久国产成人精品| 久久成人18免费观看| 国产精品久久久一区二区| 亚洲精品中文字幕在线| 99国内精品久久久久久久软件| 老**午夜毛片一区二区三区| 久久久久久久久一区二区| 国产精品自在线| 亚洲欧美日韩国产综合| 亚洲欧美不卡| 国产精品区一区| 亚洲男人第一网站| 午夜视频一区二区| 国产乱肥老妇国产一区二| 亚洲婷婷在线| 欧美一区二区三区的| 国产日韩一区| 久久久久久久久久码影片| 欧美福利一区二区| 亚洲精品国产精品国产自| 欧美日本国产视频| 一卡二卡3卡四卡高清精品视频| 一区二区三区欧美视频| 国产精品成人aaaaa网站| 亚洲欧美日韩一区二区| 欧美在线一二三四区| 一色屋精品亚洲香蕉网站| 美女尤物久久精品| 日韩亚洲欧美成人| 久久se精品一区二区| 在线观看亚洲视频啊啊啊啊| 久久综合伊人77777尤物| 亚洲精品亚洲人成人网| 亚洲欧美日韩国产中文在线| 国产一区亚洲| 欧美日韩国产小视频| 亚洲一区二区三区免费观看| 久久男人av资源网站| 亚洲精品一区中文| 国产精品综合不卡av| 久久琪琪电影院| 一区二区三欧美| 久久亚洲精品一区| 中国亚洲黄色| 一区在线电影| 欧美性猛交xxxx乱大交蜜桃| 久久精品国产99国产精品澳门| 亚洲激情午夜| 久久这里只精品最新地址| 欧美激情一区二区三区| 午夜视频精品| 日韩亚洲欧美中文三级| 国产亚洲一区二区在线观看| 欧美a级片网| 午夜免费电影一区在线观看| 最新国产の精品合集bt伙计| 久久国产精品第一页| 亚洲久色影视| 黑人巨大精品欧美一区二区| 欧美午夜影院| 欧美激情网友自拍| 久久精品在线播放| 亚洲系列中文字幕| 亚洲激情图片小说视频| 免费不卡欧美自拍视频| 欧美一区二区在线看| 这里只有精品丝袜| 91久久精品美女高潮| 韩国免费一区| 国产日产欧美一区| 欧美午夜视频| 欧美日韩1234| 欧美肥婆在线| 久久婷婷国产综合国色天香| 性久久久久久久| 亚洲欧美中文日韩在线| 亚洲最新在线视频| 亚洲精品韩国| 亚洲国内精品| 亚洲国产精品精华液2区45| 麻豆成人在线观看| 久久亚洲综合色| 久久天堂精品| 久久亚洲私人国产精品va媚药| 欧美影院在线播放| 欧美一区二区三区在| 午夜精品久久久久久久久久久久久| 一区二区三区av| 亚洲午夜未删减在线观看| av成人免费观看| 亚洲视频成人| 亚洲综合导航| 性色av一区二区三区| 欧美一级二级三级蜜桃| 欧美亚洲一区| 久久噜噜噜精品国产亚洲综合| 久久精品论坛| 欧美电影免费观看网站| 欧美激情亚洲精品| 亚洲精品一区中文| 中文网丁香综合网| 午夜精品久久久久久久久久久| 午夜在线不卡| 久久一区亚洲| 欧美日韩国产综合视频在线观看| 欧美日韩伦理在线免费| 欧美日韩影院| 国产色爱av资源综合区| 狠狠色噜噜狠狠狠狠色吗综合| 在线视频国内自拍亚洲视频| 亚洲精品久久久久| 亚洲欧美成人综合| 久热精品视频在线观看一区| 欧美高清视频在线观看| 99re6热只有精品免费观看| 亚洲一区二区免费在线| 久久精品免视看| 欧美激情亚洲视频| 国产情人综合久久777777| 在线欧美视频| 亚洲一区二区黄色| 久久综合久久久久88| 亚洲精品视频免费在线观看| 亚洲欧美影院| 欧美精品在线视频观看| 国产日韩综合| 99re66热这里只有精品4| 午夜在线精品偷拍| 欧美国产精品人人做人人爱| 一本大道久久精品懂色aⅴ| 久久不射中文字幕| 欧美日精品一区视频| 亚洲国产另类久久精品| 午夜精品久久久久久久久久久| 亚洲大片av| 欧美一区二区三区久久精品茉莉花| 欧美日韩a区| 亚洲成人在线免费| 欧美在线观看视频在线| 日韩一本二本av| 看片网站欧美日韩| 狠狠色丁香婷婷综合影院| 亚洲欧美另类久久久精品2019| 欧美激情一区在线观看| 欧美一区免费视频|