当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

1549:Bright Bracelet

题目描述

Bracelet 1

Bracelet 2


Bracelets can be made from a collection of octagonal pieces, with two opposite sides of an octagon attached to octagons on either side. The colors of the edges of the octagons vary. The different colors are labeled with different letters in the diagrams. Bracelets only look good if the connecting sides of two adjacent octagons are the same color. Above are two possible bracelets. (The ends also get fastened together.) These two bracelets could be made from the same four octagons, reordered and rotated. Assume that the octagons are never flipped over.

It happens that the better selling bracelets are those with the darker colors on the edges connecting the bracelet. The brightness of each lettered color is a positive integer, with higher numbers being brighter. Suppose the brightness of the labeled colors are:
A B C D E F G H
70 90 10 50 60 30 20 40

We can compare the desirability of these two arrangements of the octagons by adding the brightness of the colors at each joint (including the connection of the two ends). For Bracelet 1, colors A, A, E, and E have sum 70 + 70 + 60 + 60 = 260. For Bracelet 2, colors C, C, G, and E have sum 10 + 10 + 20 + 60 = 100. Bracelet 2 is preferable, having the smaller sum. In fact, Bracelet 2 provides the best possible result among all rearrangements and rotations of these four octagons.

输入解释
There are from one to 20 data sets, followed by a final line containing only 0. A data set starts with a line containing nine blank-separated integers. The first is the number, n, of octagons that form the bracelet, where 4 <= n <= 11. The remaining eight numbers are the brightness for colors A through H, in order. Each brightness is positive and less than 256.

The next n lines each contain eight letters, all in the range from A through H. Each gives the edge colors for one octagon, in clockwise order. Individual colors may appear zero or more times in the octagons. Different colors may have the same brightness, but that does not make them the same color.
输出解释
The output contains one line for each data set: If no bracelet can be constructed using all the octagons, the line contains "impossible". Otherwise the line contains the minimal sum of the brightness for the connections. Caution: If your solution considers all possible orderings and rotations individually, it will run out of time.
输入样例
4 70 90 10 50 60 30 20 40
ACACACAC
ABCDEFGH
EEEEECCC
EECCAGGG
5 1 2 3 4 5 6 7 8
AAAABBBB
BBBBCCCC
CCCCDDDD
DDDDEEEE
EEEEAAAA
6 50 50 50 50 100 1 2 3
HHHHHHHH
BBBBCCCC
CDCDDDDD
DEDEEEEE
EFEFEFEF
FFFFFFFF
0
输出样例
100
15
impossible

该题目是Virtual Judge题目,来自 北京大学POJ

题目来源 Mid-Central USA 2003

源链接: POJ-1549

最后修改于 2020-10-29T06:07:03+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
3000 65536