亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

[Ioi2007]Miners 礦工配餐(BZOJ1806)

系統(tǒng) 2393 0

[Ioi2007]Miners 礦工配餐

Time Limit:? 10 Sec?? Memory Limit:? 64 MB
Submit:? 214?? Solved:? 128

Description

現(xiàn)有兩個(gè)煤礦,每個(gè)煤礦都雇用一組礦工。采煤工作很辛苦,所以礦工們需要良好飲食。每當(dāng)一輛食品車(chē)到達(dá)煤礦時(shí),礦工們便會(huì)產(chǎn)出一定數(shù)量的煤。有三種類(lèi)型的食品車(chē):肉車(chē),魚(yú)車(chē)和面包車(chē)。 礦工們喜歡變化的食譜。如果提供的食品能夠不斷變化,他們的產(chǎn)煤量將會(huì)增加。每當(dāng)一個(gè)新的食品車(chē)到達(dá)煤礦時(shí),礦工們就會(huì)比較這種新的食品和前兩次(或者少于兩次,如果前面運(yùn)送食品的次數(shù)不足兩次)的食品,并且: ? 如果這幾次食品車(chē)都是同一類(lèi)型的食品,則礦工們產(chǎn)出一個(gè)單位的煤。 ? 如果這幾次食品車(chē)中有兩種不同類(lèi)型的食品,則礦工們產(chǎn)出兩個(gè)單位的煤。 ? 如果這幾次食品車(chē)中有三種不同類(lèi)型的食品,則礦工們產(chǎn)出三個(gè)單位的煤。 預(yù)先已知食品車(chē)的類(lèi)型及其被配送的順序。通過(guò)確定哪車(chē)食品送到哪個(gè)煤礦可以影響產(chǎn)煤量。食品車(chē)不能被拆分,每個(gè)食品車(chē)必須被全部送到一個(gè)或另一個(gè)煤礦。兩個(gè)煤礦也并不要求接收相同數(shù)量的食品車(chē)(事實(shí)上,也允許將所有食品車(chē)都送到一個(gè)煤礦)。 任務(wù) 給出食品車(chē)的類(lèi)型及其被配送的順序,要求你寫(xiě)一個(gè)程序,確定哪個(gè)食品車(chē)應(yīng)被送到煤礦1,哪個(gè)食品車(chē)應(yīng)被送到煤礦2,以使得兩個(gè)煤礦的產(chǎn)煤量的總和最大。

Input

輸入的第一行包含一個(gè)整數(shù)N (1 ≤ N ≤ 100 000), 表示食品車(chē)的數(shù)目。 第二行包含一個(gè)由N個(gè)字符組成的字符串,按照配送順序依次表示食品車(chē)配送的食品的類(lèi)型。每個(gè)字符是以下三個(gè)大寫(xiě)字母之一:'M' (表示肉類(lèi)), 'F' (表示魚(yú)類(lèi)) 或 'B' (表示面包)。

Output

輸出一個(gè)整數(shù),表示最大的總產(chǎn)煤量。 評(píng)分 在45分的測(cè)試數(shù)據(jù)中,食品車(chē)的數(shù)目至多為20

Sample Input

6
MBMFFB


Sample Output

12

HINT

?

Source

Day2

?

題解:

線性動(dòng)態(tài)規(guī)劃。根據(jù)題意以及數(shù)據(jù)規(guī)模,維護(hù)一個(gè)五維數(shù)組f[i][a][b][c][d],代表第i車(chē)食物,A煤礦前兩次食物分別是a(第二次),b(第一次),B煤礦前兩次食物分別為c,d的最大產(chǎn)煤量。注意初始化和某煤礦第一車(chē)和第二車(chē)食物的處理以及產(chǎn)煤量計(jì)算。根據(jù)動(dòng)態(tài)規(guī)劃的無(wú)后效性,可以用滾動(dòng)數(shù)組進(jìn)行優(yōu)化。

動(dòng)態(tài)轉(zhuǎn)移方程:

f[i%4][tran(ch)][a][c][d]=max(f[i%4][tran(ch)][a][c][d], f[(i-1)%4][a][b][c][d]+effort(tran(ch),a,b));

f[i%4][a][b][tran(ch)][c]=max(f[i%4][a][b][tran(ch)][c], f[(i-1)%4][a][b][c][d]+effort(tran(ch),c,d));

代碼:

        
            1
        
         #include<stdio.h>


        
            2
        
         #include<
        
          string
        
        .h>


        
            3
        
        
          int
        
        
           i,n,a,b,c,d,maxi,


        
        
            4
        
             f[
        
          5
        
        ][
        
          4
        
        ][
        
          4
        
        ][
        
          4
        
        ][
        
          4
        
        
          ];


        
        
            5
        
        
            6
        
        
          char
        
        
           ch;


        
        
            7
        
        
            8
        
        
          int
        
        
            9
        
        
          pre()


        
        
           10
        
        
          {


        
        
           11
        
             memset(f,
        
          255
        
        ,
        
          sizeof
        
        
          (f));


        
        
           12
        
             f[
        
          0
        
        ][
        
          0
        
        ][
        
          0
        
        ][
        
          0
        
        ][
        
          0
        
        ]=
        
          0
        
        
          ;


        
        
           13
        
        
          return
        
        
          0
        
        
          ;


        
        
           14
        
        
          }


        
        
           15
        
        
           16
        
        
          int
        
        
           17
        
         max(
        
          int
        
         a,
        
          int
        
        
           b)


        
        
           18
        
        
          {


        
        
           19
        
        
          if
        
        (a>b) 
        
          return
        
        
          (a);


        
        
           20
        
        
          else
        
        
          return
        
        
          (b);


        
        
           21
        
        
          }


        
        
           22
        
        
           23
        
        
          int
        
        
           24
        
         tran(
        
          char
        
        
           ch)


        
        
           25
        
        
          {


        
        
           26
        
        
          if
        
        (ch==
        
          '
        
        
          M
        
        
          '
        
        ) 
        
          return
        
        (
        
          1
        
        
          );


        
        
           27
        
        
          if
        
        (ch==
        
          '
        
        
          B
        
        
          '
        
        ) 
        
          return
        
        (
        
          2
        
        
          );


        
        
           28
        
        
          return
        
        (
        
          3
        
        
          );


        
        
           29
        
        
          }


        
        
           30
        
        
           31
        
        
          int
        
        
           32
        
         effort(
        
          int
        
         a,
        
          int
        
         b,
        
          int
        
        
           c)


        
        
           33
        
        
          {


        
        
           34
        
        
          if
        
        ((a!=
        
          0
        
        )&&(b!=
        
          0
        
        )&&(c!=
        
          0
        
        
          ))


        
        
           35
        
        
              {


        
        
           36
        
        
          if
        
        ((a==b)&&(b==c)) 
        
          return
        
        (
        
          1
        
        
          );


        
        
           37
        
        
          if
        
        ((a!=b)&&(b!=c)&&(a!=c)) 
        
          return
        
        (
        
          3
        
        
          );


        
        
           38
        
        
          return
        
        (
        
          2
        
        
          );


        
        
           39
        
        
              }


        
        
           40
        
        
          if
        
        (c==
        
          0
        
        
          )


        
        
           41
        
        
              {


        
        
           42
        
        
          if
        
        (b!=
        
          0
        
        
          )


        
        
           43
        
        
              {


        
        
           44
        
        
          if
        
        (a==b) 
        
          return
        
        (
        
          1
        
        
          );


        
        
           45
        
        
          return
        
        (
        
          2
        
        
          );


        
        
           46
        
             } 
        
          else
        
        
           47
        
        
          return
        
        (
        
          1
        
        
          );


        
        
           48
        
        
              }


        
        
           49
        
        
          }


        
        
           50
        
        
           51
        
        
           52
        
        
          int
        
        
           53
        
         dp(
        
          char
        
        
           ch)


        
        
           54
        
        
          {


        
        
           55
        
        
          for
        
        (a=
        
          0
        
        ;a<=
        
          3
        
        ;a++
        
          )


        
        
           56
        
        
          for
        
        (b=
        
          0
        
        ;b<=
        
          3
        
        ;b++
        
          )


        
        
           57
        
        
          for
        
        (c=
        
          0
        
        ;c<=
        
          3
        
        ;c++
        
          )


        
        
           58
        
        
          for
        
        (d=
        
          0
        
        ;d<=
        
          3
        
        ;d++
        
          )


        
        
           59
        
        
          if
        
        (f[(i-
        
          1
        
        )%
        
          4
        
        ][a][b][c][d]!=-
        
          1
        
        
          )


        
        
           60
        
        
                              { 


        
        
           61
        
                                 f[i%
        
          4
        
        ][tran(ch)][a][c][d]=max(f[i%
        
          4
        
        
          ][tran(ch)][a][c][d],


        
        
           62
        
                                                             f[(i-
        
          1
        
        )%
        
          4
        
        ][a][b][c][d]+
        
          effort(tran(ch),a,b));


        
        
           63
        
                                 f[i%
        
          4
        
        ][a][b][tran(ch)][c]=max(f[i%
        
          4
        
        
          ][a][b][tran(ch)][c],


        
        
           64
        
                                                             f[(i-
        
          1
        
        )%
        
          4
        
        ][a][b][c][d]+
        
          effort(tran(ch),c,d));


        
        
           65
        
        
                              }


        
        
           66
        
        
           67
        
        
           68
        
        
          return
        
        (
        
          0
        
        
          );


        
        
           69
        
        
           70
        
        
          }


        
        
           71
        
        
           72
        
        
           73
        
        
          int
        
        
           74
        
        
          init()


        
        
           75
        
        
          {


        
        
           76
        
             scanf(
        
          "
        
        
          %d\n
        
        
          "
        
        ,&
        
          n);


        
        
           77
        
        
          for
        
        (i=
        
          1
        
        ;i<=n;i++
        
          )


        
        
           78
        
        
              {


        
        
           79
        
              scanf(
        
          "
        
        
          %c
        
        
          "
        
        ,&
        
          ch);


        
        
           80
        
        
               dp(ch);


        
        
           81
        
        
              }


        
        
           82
        
        
           83
        
             maxi=-
        
          351111
        
        
          ;


        
        
           84
        
        
          for
        
        (a=
        
          0
        
        ;a<=
        
          3
        
        ;a++
        
          )


        
        
           85
        
        
          for
        
        (b=
        
          0
        
        ;b<=
        
          3
        
        ;b++
        
          )


        
        
           86
        
        
          for
        
        (c=
        
          0
        
        ;c<=
        
          3
        
        ;c++
        
          )


        
        
           87
        
        
          for
        
        (d=
        
          0
        
        ;d<=
        
          3
        
        ;d++
        
          )


        
        
           88
        
                         maxi=max(maxi,f[n%
        
          4
        
        
          ][a][b][c][d]);


        
        
           89
        
             printf(
        
          "
        
        
          %d\n
        
        
          "
        
        
          ,maxi);


        
        
           90
        
        
          return
        
        
          0
        
        
          ;


        
        
           91
        
        
          }


        
        
           92
        
        
           93
        
        
          int
        
        
           94
        
        
          main()


        
        
           95
        
        
          {


        
        
           96
        
        
              pre();


        
        
           97
        
        
              init();


        
        
           98
        
        
          return
        
        
          0
        
        
          ;


        
        
           99
        
        
          }


        
        
          100
        
      

?

?

[Ioi2007]Miners 礦工配餐(BZOJ1806)


更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號(hào)聯(lián)系: 360901061

您的支持是博主寫(xiě)作最大的動(dòng)力,如果您喜歡我的文章,感覺(jué)我的文章對(duì)您有幫助,請(qǐng)用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點(diǎn)擊下面給點(diǎn)支持吧,站長(zhǎng)非常感激您!手機(jī)微信長(zhǎng)按不能支付解決辦法:請(qǐng)將微信支付二維碼保存到相冊(cè),切換到微信,然后點(diǎn)擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對(duì)您有幫助就好】

您的支持是博主寫(xiě)作最大的動(dòng)力,如果您喜歡我的文章,感覺(jué)我的文章對(duì)您有幫助,請(qǐng)用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長(zhǎng)會(huì)非常 感謝您的哦!!!

發(fā)表我的評(píng)論
最新評(píng)論 總共0條評(píng)論
主站蜘蛛池模板: 久草看片| 91手机看片国产永久免费 | 美女在线看永久免费网址 | 久久伊人久久 | jizzjizz中国丝袜美女 | 亚洲黄色在线观看视频 | 亚洲a区视频 | 国产高清精品一区 | 亚洲另类精品综合 | 日本叼嘿 | 欧美一级毛片一级 | 久草在线视频中文 | 国产精品入口麻豆高清在线 | 欧美精品久久久久久久小说 | 99热免费在线 | sihu影院永久在线影院 | 免费看欧美毛片大片免费看 | 深夜看片在线观看18 | 日本一级爰免费视频 | 国产精品久久久久久亚洲伦理 | 成人欧美视频免费看黄黄 | 99在线热视频只有精品免费 | 91拍拍在线观看 | 爱综合网 | 亚洲你懂的 | 99热精品久久只有精品30 | 骚黄视频 | 亚洲第一激情 | 精品久久久久久久一区二区手机版 | 色偷偷精品视频在线播放 | 精品哟哟国产在线观看 | 日韩你懂得 | 日本不卡一区二区三区 | 国产精品2020观看久久 | 欧美毛片一级 | 久久九九热视频 | 1000部羞羞禁止免费观看视频 | 免费视频一级片 | 亚洲视频在线播放 | 高清一区高清二区视频 | 免费在线黄色网址 |