• <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個鞭炮放時候爆或不爆  回復  更多評論
              
            久久精品亚洲AV久久久无码| 伊色综合久久之综合久久| 伊人色综合久久天天人手人婷| 亚洲国产日韩综合久久精品| 日本加勒比久久精品| 久久www免费人成看片| 东京热TOKYO综合久久精品| 久久亚洲精品视频| 欧美午夜A∨大片久久| 热re99久久精品国99热| 欧美伊香蕉久久综合类网站| 99久久国产亚洲综合精品| 国产麻豆精品久久一二三| 中文成人久久久久影院免费观看| 久久久久亚洲av无码专区喷水| 精品久久久久久国产三级| 日日躁夜夜躁狠狠久久AV| 三级韩国一区久久二区综合| 久久精品中文字幕无码绿巨人| 91精品国产高清久久久久久91 | 久久亚洲精品中文字幕| 国产精品免费久久| 久久ww精品w免费人成| 久久综合久久美利坚合众国| 国产99久久久久久免费看| 国产成年无码久久久久毛片| 久久精品国产亚洲AV忘忧草18| 99热热久久这里只有精品68| 99久久婷婷免费国产综合精品| 99久久无色码中文字幕人妻| 一本色综合久久| 久久伊人精品一区二区三区| 久久精品国产亚洲AV不卡| 超级碰久久免费公开视频| 精品久久久久久国产| a级成人毛片久久| 成人资源影音先锋久久资源网| 欧美黑人激情性久久| 亚洲va久久久噜噜噜久久狠狠| 久久婷婷五月综合97色直播| 久久精品国产男包|