[Ioi2007]Miners 礦工配餐
Time Limit:? 10 Sec?? Memory Limit:? 64 MBSubmit:? 214?? Solved:? 128
Description
Input
Output
Sample Input
MBMFFB
Sample Output
HINT
Source
?
題解:
線性動(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
?
?
更多文章、技術(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ì)您有幫助就好】元
