[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ì)您有幫助就好】元
