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
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
