• <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>
            隨筆 - 87  文章 - 279  trackbacks - 0
            <2006年4月>
            2627282930311
            2345678
            9101112131415
            16171819202122
            23242526272829
            30123456

            潛心看書研究!

            常用鏈接

            留言簿(19)

            隨筆分類(81)

            文章分類(89)

            相冊

            ACM OJ

            My friends

            搜索

            •  

            積分與排名

            • 積分 - 217940
            • 排名 - 117

            最新評論

            閱讀排行榜

            評論排行榜

            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 閱讀(578) 評論(0)  編輯 收藏 引用 所屬分類: ACM題目
            亚洲AV无码一区东京热久久| 97精品伊人久久久大香线蕉| 日韩美女18网站久久精品| 偷偷做久久久久网站| 69SEX久久精品国产麻豆| 久久99久久99小草精品免视看| 午夜肉伦伦影院久久精品免费看国产一区二区三区 | 色狠狠久久AV五月综合| 久久精品国产黑森林| 国产亚洲欧美精品久久久| 欧美亚洲国产精品久久| 久久99热这里只有精品国产| 久久国产成人精品麻豆| 人妻丰满?V无码久久不卡| 久久天堂AV综合合色蜜桃网 | 亚州日韩精品专区久久久| 亚洲国产精品久久电影欧美| 国产精品美女久久久久av爽| 久久精品aⅴ无码中文字字幕重口| 四虎亚洲国产成人久久精品| 久久精品中文騷妇女内射| 久久婷婷五月综合97色直播| 国产精品VIDEOSSEX久久发布| 久久人妻无码中文字幕| 亚洲成色www久久网站夜月| 国产精品成人99久久久久91gav| 色综合久久久久无码专区| 色偷偷91久久综合噜噜噜噜| 国产精品久久久天天影视| 久久精品亚洲日本波多野结衣| 99久久香蕉国产线看观香| 久久99精品久久久久久水蜜桃| 狠色狠色狠狠色综合久久| 久久人人添人人爽添人人片牛牛 | 少妇久久久久久被弄高潮| 思思久久精品在热线热| 三级片免费观看久久| 午夜视频久久久久一区| 人妻精品久久久久中文字幕| 久久久久亚洲AV无码专区桃色| 国产成人精品久久一区二区三区av|