• <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年6月>
            25262728293031
            1234567
            891011121314
            15161718192021
            22232425262728
            293012345

            潛心看書研究!

            常用鏈接

            留言簿(19)

            隨筆分類(81)

            文章分類(89)

            相冊

            ACM OJ

            My friends

            搜索

            •  

            積分與排名

            • 積分 - 217755
            • 排名 - 117

            最新評論

            閱讀排行榜

            評論排行榜

            開始時(shí)候粗心,狀態(tài)轉(zhuǎn)移時(shí)候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
            我是一個(gè)剛剛開始做acm題的菜鳥,望大哥幫幫忙,可以介紹一下解決的思想嗎?小弟先謝謝了!  回復(fù)  更多評論
              
            # re: pku2904 3維dp 2007-03-27 23:04 
            dp[k][i][j]表示k個(gè)郵筒時(shí)候放鞭炮數(shù)為i..j時(shí)候的最優(yōu)值

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

            狀態(tài)轉(zhuǎn)移時(shí)候就是考慮選t個(gè)鞭炮放時(shí)候爆或不爆  回復(fù)  更多評論
              
            久久www免费人成看片| 精品久久久久久综合日本| 久久久久97国产精华液好用吗| 99久久精品免费看国产| 伊人久久大香线蕉无码麻豆| 亚洲成色WWW久久网站| 9191精品国产免费久久| 久久精品中文字幕一区| 久久婷婷综合中文字幕| 蜜桃麻豆WWW久久囤产精品| 久久w5ww成w人免费| 久久久久97国产精华液好用吗| 久久99精品久久久久久久久久| 少妇久久久久久被弄到高潮| 久久精品国产亚洲av麻豆色欲 | 国产巨作麻豆欧美亚洲综合久久| 午夜福利91久久福利| 国产精品久久成人影院| 中文字幕热久久久久久久| 久久性生大片免费观看性| 国产综合久久久久| 精品久久久久久中文字幕大豆网| 久久丝袜精品中文字幕| 久久精品国产亚洲麻豆| 国产精品一久久香蕉国产线看观看| 久久国产欧美日韩精品免费| 狠狠人妻久久久久久综合蜜桃| 69SEX久久精品国产麻豆| 日本强好片久久久久久AAA| 久久青青草视频| 久久99国产精品久久99小说 | 99久久人妻无码精品系列蜜桃 | 三级韩国一区久久二区综合 | 97精品国产97久久久久久免费| 无码国内精品久久人妻蜜桃| 精品综合久久久久久97| 无码任你躁久久久久久老妇App| 久久伊人五月天论坛| 久久精品无码专区免费| 无码精品久久一区二区三区 | 狠狠色丁香婷婷久久综合不卡|