[Ioi2007]Miners 礦工配餐
Time Limit:? 10 Sec?? Memory Limit:? 64 MBSubmit:? 214?? Solved:? 128
Description
Input
Output
Sample Input
MBMFFB
Sample Output
HINT
Source
?
題解：
線性動態規劃。根據題意以及數據規模，維護一個五維數組f[i][a][b][c][d],代表第i車食物，A煤礦前兩次食物分別是a(第二次),b(第一次)，B煤礦前兩次食物分別為c,d的最大產煤量。注意初始化和某煤礦第一車和第二車食物的處理以及產煤量計算。根據動態規劃的無后效性，可以用滾動數組進行優化。
動態轉移方程：
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
?
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
