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

隨筆 - 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资源综合区| 欧美激情一区二区三区| 欧美午夜不卡| 欧美aa在线视频| 欧美日韩国产探花| 久久久噜噜噜久久狠狠50岁| 欧美国产免费| 久久精品主播| 久久综合中文字幕| 欧美激情中文字幕一区二区| 国产免费成人av| 欧美成人免费网| 国产精品久久久久一区二区三区共 | 亚洲美女尤物影院| 国产一区三区三区| 亚洲精品一区中文| 黄色亚洲免费| 亚洲九九爱视频| 亚洲第一福利在线观看| 亚洲视频精品| 亚洲精品色婷婷福利天堂| 亚洲图片欧洲图片日韩av| 亚洲国产精品嫩草影院| 亚洲欧美在线观看| 一区二区三区久久网| 久久五月天婷婷| 久久爱91午夜羞羞| 欧美天天在线| 亚洲激情在线视频| 狠狠干综合网| 亚洲一区欧美| 亚洲综合色噜噜狠狠| 暖暖成人免费视频| 麻豆视频一区二区| 国内激情久久| 欧美伊久线香蕉线新在线| 亚洲图片欧洲图片日韩av| 欧美激情欧美激情在线五月| 欧美成人午夜剧场免费观看| 国产一区二区激情| 亚洲欧美在线磁力| 久久成人羞羞网站| 国产精品尤物| 亚洲欧美国产毛片在线| 亚洲欧美成人在线| 国产精品成人一区| 亚洲视频999| 亚洲欧美日韩国产一区二区三区| 欧美成人情趣视频| 亚洲国产精品久久久久久女王| 亚洲高清一二三区| 久久综合伊人77777蜜臀| 毛片基地黄久久久久久天堂| 国产专区一区| 久久综合色影院| 欧美激情中文字幕一区二区| 亚洲国产裸拍裸体视频在线观看乱了| 欧美一区二区观看视频| 久久不射网站| 亚洲大胆在线| 欧美激情偷拍| 中日韩午夜理伦电影免费| 亚洲制服丝袜在线| 国产欧美一区二区三区沐欲| 亚洲欧美另类中文字幕| 久久精品国产亚洲5555| 伊人久久综合| 欧美紧缚bdsm在线视频| 在线视频精品一区| 久久av资源网| 亚洲风情亚aⅴ在线发布| 美日韩丰满少妇在线观看| 亚洲国产日韩精品| 亚洲在线观看免费| 国产欧美日韩激情| 久久天天躁狠狠躁夜夜爽蜜月| 亚洲国产日韩欧美一区二区三区| 亚洲一级特黄| 狠狠色狠狠色综合日日五| 狂野欧美激情性xxxx| 亚洲开发第一视频在线播放| 久久都是精品| 亚洲日本欧美| 国产精品网站在线观看| 久久这里有精品视频| 亚洲深夜福利网站| 欧美电影免费观看| 午夜在线不卡| 日韩视频免费| 韩日午夜在线资源一区二区| 欧美日韩国产专区| 久久久91精品国产一区二区三区| 亚洲精品国产精品国产自| 欧美在线一二三| 99ri日韩精品视频| 国内精品伊人久久久久av影院| 欧美久久久久久久久久| 久久黄色小说| 亚洲免费在线看| 99视频国产精品免费观看| 麻豆精品视频在线观看| 性做久久久久久免费观看欧美| 亚洲欧洲一区二区在线观看| 国产一区亚洲| 国产精品久久久久9999| 欧美激情bt| 美女诱惑一区| 久久午夜羞羞影院免费观看| 午夜久久久久久| 亚洲小说春色综合另类电影| 亚洲人成在线观看一区二区| 老司机精品视频网站| 欧美一级久久久| 亚洲午夜视频| 宅男精品视频| 一区二区三区毛片| 亚洲免费电影在线| 亚洲精品国产精品国产自| 一区在线电影| 在线欧美亚洲| 在线观看一区二区精品视频| 国产亚洲欧美日韩精品| 国产日本欧美一区二区| 国产精品一区亚洲| 国产精品区二区三区日本 | 久久午夜视频| 美女图片一区二区| 美日韩免费视频| 久久夜色精品亚洲噜噜国产mv| 欧美影院一区| 欧美中文字幕在线观看| 亚洲欧美另类中文字幕| 午夜精品久久久久久久蜜桃app| 宅男66日本亚洲欧美视频| av成人毛片| 亚洲一区二区不卡免费| 亚洲午夜激情网页| 亚洲欧美在线免费| 久久精品国产清高在天天线 | 一本色道久久综合亚洲精品婷婷 | 久久午夜国产精品| 欧美成人激情视频| 欧美韩日精品| 亚洲精品美女在线观看| 99伊人成综合| 午夜精品www| 久久天天综合| 欧美日韩精品三区| 国产乱肥老妇国产一区二 | 欧美韩日一区二区三区| 欧美日韩麻豆| 国产亚洲成av人片在线观看桃| 黄色小说综合网站| 亚洲免费观看高清完整版在线观看熊| 亚洲深爱激情| 久久久久久久综合| 亚洲电影有码| 亚洲中无吗在线| 久久看片网站| 国产精品福利影院| 韩日欧美一区| 亚洲香蕉网站| 欧美成年人网| 亚洲少妇诱惑| 欧美电影专区| 国产视频一区在线观看一区免费| 在线精品视频一区二区三四| 一区二区三区日韩精品| 久久久精品性| av成人免费在线| 美女成人午夜| 国产最新精品精品你懂的| 日韩一级精品视频在线观看| 久久精品综合| 一本色道久久88精品综合| 久久婷婷久久| 国产毛片一区| 亚洲在线中文字幕| 亚洲福利小视频| 久久九九免费视频| 国产精品一区二区三区成人| 夜久久久久久| 亚洲第一伊人| 久久亚洲春色中文字幕久久久| 国产精品久久中文| 一本久久综合亚洲鲁鲁| 欧美激情一区二区三区在线视频观看| 欧美一区二区三区播放老司机|