• <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
            <2025年7月>
            293012345
            6789101112
            13141516171819
            20212223242526
            272829303112
            3456789

            潛心看書研究!

            常用鏈接

            留言簿(19)

            隨筆分類(81)

            文章分類(89)

            相冊

            ACM OJ

            My friends

            搜索

            •  

            積分與排名

            • 積分 - 217881
            • 排名 - 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題目
            午夜精品久久久久久99热| 人人狠狠综合久久亚洲88| 亚洲精品午夜国产va久久| 久久综合亚洲色HEZYO国产| 伊人色综合久久天天网| 亚洲综合日韩久久成人AV| 伊人色综合久久天天| 国产69精品久久久久观看软件 | 亚洲AⅤ优女AV综合久久久| 日韩va亚洲va欧美va久久| 久久婷婷国产综合精品| 国产AV影片久久久久久| 少妇人妻综合久久中文字幕| 九九久久99综合一区二区| 久久久久av无码免费网| 久久不见久久见免费影院www日本| 久久笫一福利免费导航| 91麻精品国产91久久久久| 亚洲中文久久精品无码| 欧美久久一级内射wwwwww.| 久久精品中文字幕久久| 久久青青草原亚洲av无码app| 久久久久国色AV免费观看| 久久综合丁香激情久久| 少妇久久久久久被弄高潮| 亚洲欧美国产精品专区久久| 国产69精品久久久久99尤物| 97精品国产91久久久久久| 久久午夜伦鲁片免费无码| 99久久国产精品免费一区二区 | 99久久精品国产高清一区二区 | 久久综合久久综合久久综合| 久久久久久人妻无码| 少妇人妻88久久中文字幕| 精品国产乱码久久久久久人妻| 综合久久精品色| 欧美麻豆久久久久久中文| 一本大道久久香蕉成人网| 成人综合久久精品色婷婷| 久久人人爽人人人人爽AV | 久久人妻无码中文字幕|