• <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
            <2007年2月>
            28293031123
            45678910
            11121314151617
            18192021222324
            25262728123
            45678910

            潛心看書研究!

            常用鏈接

            留言簿(19)

            隨筆分類(81)

            文章分類(89)

            相冊

            ACM OJ

            My friends

            搜索

            •  

            積分與排名

            • 積分 - 217985
            • 排名 - 117

            最新評論

            閱讀排行榜

            評論排行榜

            開始時候粗心,狀態轉移時候k寫成k-1了,查了n久.

            The Mailboxes Manufacturers Problem
            Time Limit:1000MS? Memory Limit:65536K
            Total Submit:299 Accepted:227

            Description

            In the good old days when Swedish children were still allowed to blowup their fingers with fire-crackers, gangs of excited kids would plague certain smaller cities during Easter time, with only one thing in mind: To blow things up. Small boxes were easy to blow up, and thus mailboxes became a popular target. Now, a small mailbox manufacturer is interested in how many fire-crackers his new mailbox prototype can withstand without exploding and has hired you to help him. He will provide you with k (1 ≤ k ≤ 10) identical mailbox prototypes each fitting up to m (1 ≤ m ≤ 100) crackers. However, he is not sure of how many firecrackers he needs to provide you with in order for you to be able to solve his problem, so he asks you. You think for a while and then say, “Well,if I blow up a mailbox I can’t use it again, so if you would provide me with only k = 1 mailboxes, I would have to start testing with 1 cracker, then 2 crackers, and so on until it finally exploded. In the worst case, that is if it does not blow up even when filled with m crackers, I would need 1 + 2 + 3 + … + m = m × (m + 1) ? 2 crackers. If m = 100 that would mean more than 5000 fire-crackers!” “That’s too many,” he replies. “What if I give you more than k = 1 mailboxes? Can you find a strategy that requires less crackers?”

            Can you? And what is the minimum number of crackers that you should ask him to provide you with?

            You may assume the following:

            1. If a mailbox can withstand x fire-crackers, it can also withstand x ? 1 fire-crackers.
            2. Upon an explosion, a mailbox is either totally destroyed (blown up) or unharmed, which means that it can be reused in another test explosion.

            Note: If the mailbox can withstand a full load of m fire-crackers, then the manufacturer will of course be satisfied with that answer. But otherwise he is looking for the maximum number of crackers that his mailboxes can withstand.

            Input

            The input starts with a single integer N (1 ≤ N ≤ 10) indicating the number of test cases to follow. Each test case is described by a line containing two integers: k and m, separated by a single space.

            Output

            For each test case print one line with a single integer indicating the minimum number of fire-crackers that is needed, in the worst case, in order to figure out how many crackers the mailbox prototype can withstand.

            Sample Input

            4
            1 10
            1 100
            3 73
            5 100

            Sample Output

            55
            5050
            382
            495

            Source
            Svenskt M?sterskap i Programmering/Norgesmesterskapet 2002

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

            const?int?INF?=?1?<<?28;

            int?d[11][101][101];
            int?sum(int?i,?int?j)?{
            ????
            int?ret?=?0,?k;
            ????
            for?(k=i;?k<=j;?k++)?ret?+=?k;
            ????return?ret;
            }

            int?max(int?a,?int?b)?{
            ????return?a?
            >?b???a?:?b;
            }


            int?main()?{
            ????
            int?caseTime;?
            ????
            int?i,?j,?k,?t,?K,?M,?l;
            ????scanf(
            "%d",?&caseTime);
            ????
            ????
            while?(caseTime--)?{
            ????????scanf(
            "%d%d",?&K,?&M);
            ????????
            for?(i=1;?i<=M;?i++)?{
            ????????????
            for?(j=i;?j<=M;?j++)?{
            ????????????????d[
            1][i][j]?=?sum(i,?j);
            ????????????}
            ????????}
            ????????
            for?(k=2;?k<=K;?k++)?{
            ????????????
            for?(l=0;?l<M;?l++)?{
            ????????????????
            for?(i=1;?i+l<=M;?i++)?{
            ????????????????????j?
            =?i?+?l;
            ????????????????????
            if?(i?==?j)?{
            ????????????????????????d[k][i][j]?
            =?i;
            ????????????????????????continue;
            ????????????????????}
            ????????????????????d[k][i][j]?
            =?INF;
            ????????????????????
            for?(t=i;?t<=j;?t++)?{
            ????????????????????????
            int?tmp;
            ????????????????????????
            if?(t?==?i)?tmp?=?d[k][i+1][j];
            ????????????????????????
            else?if?(t?==?j)?tmp?=?d[k-1][i][j-1];
            ????????????????????????
            else?tmp?=?max(d[k-1][i][t-1],?d[k-1][t+1][j]);
            ????????????????????????tmp?
            =?max(d[k-1][i][t-1],?d[k][t+1][j]);
            ????????????????????????
            if?(d[k][i][j]?>?t?+?tmp)?d[k][i][j]?=?t?+?tmp;
            ????????????????????}
            ????????????????}
            ????????????}
            ????????}
            ????????printf(
            "%d\n",?d[K][1][M]);
            ????}

            ????return?
            0;
            }
            posted on 2007-03-26 00:41 閱讀(2213) 評論(2)  編輯 收藏 引用 所屬分類: ACM題目

            FeedBack:
            # re: pku2904 3維dp 2007-03-27 16:31 litianze
            我是一個剛剛開始做acm題的菜鳥,望大哥幫幫忙,可以介紹一下解決的思想嗎?小弟先謝謝了!  回復  更多評論
              
            # re: pku2904 3維dp 2007-03-27 23:04 
            dp[k][i][j]表示k個郵筒時候放鞭炮數為i..j時候的最優值

            轉移方程為
            dp[k][i][j] = min{t+max(d[k-1][i][t-1],d[k][t+1][j])};

            狀態轉移時候就是考慮選t個鞭炮放時候爆或不爆  回復  更多評論
              
            亚洲中文久久精品无码| 久久亚洲国产中v天仙www| 狠狠色丁香久久婷婷综合蜜芽五月| 亚洲伊人久久成综合人影院| 色诱久久久久综合网ywww| 国产一区二区精品久久凹凸| 久久久无码精品亚洲日韩京东传媒| 国产韩国精品一区二区三区久久| 欧美久久一区二区三区| 欧美大香线蕉线伊人久久| 久久久久香蕉视频| 99久久中文字幕| 99精品国产免费久久久久久下载| 久久九九精品99国产精品| 亚洲美日韩Av中文字幕无码久久久妻妇 | 久久水蜜桃亚洲av无码精品麻豆 | 伊人伊成久久人综合网777| 国产美女久久精品香蕉69| 亚洲国产天堂久久综合| 激情综合色综合久久综合| 国产成人久久精品激情| 精品熟女少妇AV免费久久| 久久久久久午夜精品| 久久久久久国产精品美女| 久久精品成人免费看| 99久久精品费精品国产一区二区| 久久久一本精品99久久精品88| 性做久久久久久久久| 久久人人爽人人澡人人高潮AV| 国产三级精品久久| 国产香蕉97碰碰久久人人| 精品国产91久久久久久久a| 国产高潮久久免费观看| 久久国产一片免费观看| 国产精品欧美亚洲韩国日本久久| 久久精品一区二区| 国产三级精品久久| 一本色道久久88综合日韩精品 | 午夜天堂av天堂久久久| 久久久久久夜精品精品免费啦| 久久青青草原精品国产|