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

建议使用的浏览器:

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

4065:Catan

题目描述
The Settles of Catan is a multiplayer board game. It was one of the first German-style board games to achieve popularity outside of Europe.
The players in the game represent settlers establishing colonies on the island of Catan.Players build settlements, cities, and roads as they settle on the island. Certainly roads can connect the settlements and cities.Players build with resources such as brick, lumber, wool, grain, and ore.
Now look at the board below, do you see the hexagons tiles?

There are six kinds of tiles. Five resources are mentioned above, and one is unproductive desert.
At the beginning of a game, the hexagons tiles will be randomly settled on the board, and each tile will be randomly assigned an integer ranging from 2 to 12. The desert will always be 7.
Every turn a player rolls two six-sided dices, determining which tiles produce resources.

To simplify the problem, we consider the construction phase at the beginning of the game, each player builds two settlements in this phase:
1.We have four players identified by 1,2,3,4.
2.On the first construction phase player 1,2,3,4 take turns to build a settlement separately.
On the second construction phase player 4,3,2,1 take turns to build a settlement separately.
3.Settlements can only be built on corners of the tiles, see the picture below, you are allowed to build settlements on the 54 corners signed with 0~53.

4.Any two settlements couldn't build adjacently, that means if a settlement have been built on the corner 19, then you couldn't build another settlement on 9, 18 or 20.
5.The probability of the number rolled by two dices are different. For example, if we roll two dices 36 times, the expectation to get 6 or 8 is 5 times, while the expectation to get 2 or 12 is 1.
For example, look the picture, if I build two settlement at 32 and 20,then the expectation is 4(9) + 4(9) + 3(4) + 5(6) + 2(11) + 4(9) = 22.
6.To get better development,you should try you best to get all five kinds of resources.
7.Other players are greedy, when they turn to build settlement, they will choose the corners with highest expectation (if more than one such corners, they will choose the one with minimum sign).

Now as player 1, you should choose the best strategy for building settlement to make the expectation as high as possible.(the expectation calculated by roll two dices 36 times)
输入解释
The first line is a number T(1<=T<=50), represents the number of case. The next T blocks follow each indicates a case.
Five lines follow, indicate the situation.
'B' indicate the Brick.
'W' indicate the Wool.
'L' indicate the Lumber.
'G' indicate the Grain.
'O' indicate the Ore.
'D' indicate the Desert.
Then five lines follow.
Each number indication the number sign of this tile.
There is an empty line between cases.
输出解释
For each case, If you couldn't get all of five resource,then output -1, else output the highest expectation you could get.(as shown in the sample output)
输入样例
2
  O B B
 G W G W
O L L G G
 L D O B
  B O W
  8 10 9
 3 4 5 12
6 9 11 6 11
 2 7 3  4
  5 10 8

  B W L 
 D W L B 
L D G B D 
 L O D W 
  D G W 
  8 3 8 
 7 2 8 6 
9 7 9 8 7 
 9 3 7 6 
  7 3 8 
输出样例
Case 1: 19
Case 2: -1

提示
For case1,I will choose 18 and 45 to build settlement
来自杭电HDUOJ的附加信息
Recommend lcy

该题目是Virtual Judge题目,来自 杭电HDUOJ

源链接: HDU-4065

最后修改于 2020-10-25T23:09:47+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
3000/1000MS(Java/Others) 65536/32768K(Java/Others)