[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
