青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

隨筆 - 87  文章 - 279  trackbacks - 0
<2025年9月>
31123456
78910111213
14151617181920
21222324252627
2829301234
567891011

潛心看書研究!

常用鏈接

留言簿(19)

隨筆分類(81)

文章分類(89)

相冊

ACM OJ

My friends

搜索

  •  

積分與排名

  • 積分 - 219404
  • 排名 - 118

最新評論

閱讀排行榜

評論排行榜

開始時候粗心,狀態轉移時候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 閱讀(2223) 評論(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個鞭炮放時候爆或不爆  回復  更多評論
  
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
              亚洲国产导航| 国产精品一卡| 亚洲精品在线免费观看视频| 美女国内精品自产拍在线播放| 久久国产主播| 亚洲欧洲偷拍精品| 99成人在线| 国产偷自视频区视频一区二区| 麻豆精品视频| 欧美精品日韩三级| 午夜精品国产更新| 欧美亚洲在线播放| 亚洲人午夜精品| 亚洲一区二区精品在线| 禁久久精品乱码| 91久久久久久| 国产精品系列在线播放| 免费看亚洲片| 欧美日韩一区不卡| 久久青青草综合| 欧美日本在线一区| 久久久av毛片精品| 欧美日韩黄视频| 久久精品国产亚洲一区二区| 欧美激情第五页| 久久理论片午夜琪琪电影网| 欧美激情在线播放| 久久久www成人免费毛片麻豆| 欧美www在线| 久久久久久久久伊人| 欧美日韩美女在线| 免费成人在线视频网站| 国产精品美女久久久| 亚洲激情在线观看视频免费| 韩国成人福利片在线播放| 91久久极品少妇xxxxⅹ软件| 国内精品久久久久伊人av| 日韩一区二区免费看| 亚洲黄色av| 久久精品成人一区二区三区 | 美女成人午夜| 欧美一区日本一区韩国一区| 欧美激情视频在线播放| 乱码第一页成人| 欧美不卡激情三级在线观看| 国产欧美日韩视频| 亚洲国产日本| 一区在线视频观看| 午夜欧美精品| 午夜免费电影一区在线观看| 欧美日韩国产二区| 亚洲人成久久| 亚洲精品久久久久| 男人的天堂亚洲在线| 欧美成人综合一区| 亚洲成人在线| 久久一区免费| 亚洲电影在线| 91久久夜色精品国产九色| 久久精品国产清高在天天线 | 亚洲大胆在线| 久久久青草青青国产亚洲免观| 久久精品一区四区| 国产字幕视频一区二区| 久久国产一区二区| 久热精品视频在线观看| 激情文学综合丁香| 久久综合色一综合色88| 亚洲电影观看| 日韩午夜电影在线观看| 欧美破处大片在线视频| 夜夜嗨av色一区二区不卡| 亚洲午夜激情网页| 国产精品视频一区二区高潮| 亚洲欧美国产va在线影院| 欧美中文字幕视频在线观看| 国产视频欧美视频| 久久久不卡网国产精品一区| 免费在线亚洲| 99热在线精品观看| 国产精品久久国产精麻豆99网站| 一区二区三欧美| 久久乐国产精品| 亚洲人成在线观看| 国产精品久在线观看| 久久精品视频在线播放| 欧美激情第一页xxx| 在线视频精品| 国产乱码精品一区二区三区不卡| 久久精品99无色码中文字幕| 国产精品剧情在线亚洲| 欧美在线一二三| 黄色成人91| 欧美风情在线| 亚洲欧美在线另类| 亚洲高清网站| 欧美在线短视频| 亚洲精品久久久蜜桃 | 久久不射中文字幕| 亚洲精品综合久久中文字幕| 校园激情久久| 91久久线看在观草草青青| 国产精品久久久久久久久久三级| 久久精品亚洲精品| 99re热这里只有精品视频| 久久国产精品一区二区| av成人免费观看| 国内精品久久久| 国产精品国产三级国产aⅴ无密码| 久久久久久久欧美精品| 一区二区三区不卡视频在线观看 | 欧美精品久久久久a| 一区二区三区福利| 久久精品91| 亚洲尤物视频在线| 亚洲国产精品久久| 国产麻豆午夜三级精品| 欧美精品免费看| 久久视频一区| 欧美亚洲自偷自偷| 亚洲午夜一区二区| 亚洲精品视频在线观看网站| 麻豆freexxxx性91精品| 香港久久久电影| 亚洲小说欧美另类社区| 日韩视频在线一区| 一色屋精品亚洲香蕉网站| 国产毛片精品视频| 国产精品乱码一区二区三区| 99re6热只有精品免费观看| 国产毛片久久| 国产婷婷色一区二区三区| 欧美不卡福利| 美国三级日本三级久久99| 欧美在线日韩| 久久精品动漫| 久久精品五月| 麻豆九一精品爱看视频在线观看免费| 久久不射中文字幕| 久久久人成影片一区二区三区| 久久天天躁狠狠躁夜夜爽蜜月| 久久精品视频在线观看| 久久蜜桃精品| 欧美成年人网站| 欧美日韩国产123| 欧美日韩一级视频| 国产精品视频yy9299一区| 欧美日韩高清一区| 欧美日韩视频在线一区二区| 久热精品视频| 欧美日韩ab片| 欧美另类女人| 欧美福利专区| 国产精品久久久久久久久久久久久久 | 在线视频日韩精品| 亚洲人成亚洲人成在线观看| 在线观看国产精品淫| 欧美性色综合| 国产午夜亚洲精品理论片色戒| 国产精品日韩| 国产农村妇女精品一二区| 国产酒店精品激情| 在线播放日韩欧美| 亚洲国产精品ⅴa在线观看| 亚洲二区在线视频| 永久免费精品影视网站| 红桃视频一区| 亚洲国产精品一区| 亚洲人成人一区二区三区| 亚洲性线免费观看视频成熟| 亚洲在线观看视频网站| 香蕉乱码成人久久天堂爱免费| 久久国产精彩视频| 亚洲日本aⅴ片在线观看香蕉| 亚洲美女在线视频| 中文亚洲视频在线| 西瓜成人精品人成网站| 欧美aⅴ一区二区三区视频| 欧美精品系列| 国产精品美女久久久久久久| 亚洲国产婷婷香蕉久久久久久99| 在线视频欧美精品| 亚洲欧美高清| 美国十次成人| 欧美日韩高清区| 亚洲成人自拍视频| 亚洲精品乱码久久久久久日本蜜臀| 99亚洲一区二区| 性一交一乱一区二区洋洋av| 免费精品99久久国产综合精品| 欧美大片va欧美在线播放| 中文一区二区在线观看| 久久久久久电影| 欧美日韩免费精品| 亚洲精品免费在线播放| 篠田优中文在线播放第一区| 亚洲电影免费观看高清| 久久久精品免费视频| 欧美精品一区二区三区蜜臀| 国产视频精品网|