Time Limit:
3000 ms
Memory Limit:
10000 kB
Total Submit :
2
(1 user)
Accepted Submit :
2
(1 user)
Page View : 1582
本题其实并不难，就是记忆搜索，但是好多人都没做。最难的估计就是状态的存储，一开始的时候我用的是三维数组存储，虽然在TJU和NK上都过了，但是在北大上确实WRONG，后来我又重新开了一遍发现确实存在错误，后来将数组开到四维才在北大上顺利通过。因为本题我竟然成了NK上第一个提交此题并A的人。值得留念！
代码：
1
#include
<
stdio.h
>
2
#include
<
string
.h
>
3
char
end,str[
15
][
10
];
4
int
n,dp[
2050
][
10
][
10
][
10
],mark[
15
],a[
10
];
5
int
test(
int
sum,
char
u,
char
f,
int
c)
6
{
7
int
term,i,j,min
=
0xfffffff
;
8
if
(dp[sum][u
-
'
A
'
+
1
][f
-
'
A
'
+
1
][end
-
'
A
'
+
1
]
!=
0
)
9
return
dp[sum][u
-
'
A
'
+
1
][f
-
'
A
'
+
1
][end
-
'
A
'
+
1
];
10
if
(c
==
n)
11
{
12
if
(f
==
end)
13
return
a[(f
-
'
A
'
)
+
1
];
14
return
-
1
;
15
}
16
for
(i
=
2
;i
<=
n;i
++
)
17
{
18
if
(mark[i])
19
continue
;
20
mark[i]
=
1
;
21
for
(j
=
0
;j
<
8
;j
++
)
22
{
23
if
(f
==
str[i][j])
24
{
25
term
=
test(sum
-
(
1
<<
(i
-
1
)),f,str[i][(j
+
4
)
%
8
],c
+
1
);
26
dp[sum
-
(
1
<<
(i
-
1
))][f
-
'
A
'
+
1
][str[i][(j
+
4
)
%
8
]
-
'
A
'
+
1
][end
-
'
A
'
+
1
]
=
term;
27
if
(term
!=-
1
)
28
{
29
if
(term
+
a[f
-
'
A
'
+
1
]
<
min)
30
min
=
term
+
a[f
-
'
A
'
+
1
];
31
}
32
}
33
}
34
mark[i]
=
0
;
35
}
36
if
(min
==
0xfffffff
)
37
return
-
1
;
38
return
min;
39
}
40
41
int
main()
42
{
43
int
i,min,term,sum;
44
while
(scanf(
"
%d
"
,
&
n)
!=
EOF)
45
{
46
if
(n
==
0
)
47
break
;
48
min
=
0xfffffff
;
49
memset(mark,
0
,
sizeof
(mark));
50
memset(dp,
0
,
sizeof
(dp));
51
for
(i
=
1
;i
<=
8
;i
++
)
52
{
53
scanf(
"
%d
"
,
&
a[i]);
54
}
55
for
(i
=
1
;i
<=
n;i
++
)
56
{
57
scanf(
"
%s
"
,str[i]);
58
}
59
mark[
1
]
=
1
;
60
sum
=
(
1
<<
n)
-
1
;
61
for
(i
=
0
;i
<
4
;i
++
)
62
{
63
end
=
str[
1
][(i
+
4
)
%
8
];
64
term
=
test(sum
-
1
,str[
1
][(i
+
4
)
%
8
],str[
1
][i],
1
);
65
dp[sum
-
1
][end
-
'
A
'
+
1
][str[
1
][i]
-
'
A
'
+
1
][end
-
'
A
'
+
1
]
=
term;
66
if
(term
!=-
1
)
67
{
68
if
(term
<
min)
69
min
=
term;
70
}
71
}
72
if
(min
!=
0xfffffff
)
73
{
74
printf(
"
%d\n
"
,min);
75
}
76
else
77
printf(
"
impossible\n
"
);
78
}
79
return
0
;
80
}
81
82
83
