A13009. Tiling Terrace
编程题
普及/提高-
知识点
题目描述
Input begins with a line containing five integers: $N$ $K$ $G_1$ $G_2$ $G_3$ ( $1 \le N \le 100\,000$ ; $0 \le K \le N$ ; $0 \le G_1, G_2, G_3 \le 1000$ ) representing the number of cells, the maximum number of tiles of Type-1, the number of ghosts repelled per day by a tile of Type-1, the number of ghosts repelled per day by a tile of Type-2, and the number of ghosts repelled by a tile of Type-3, respectively. The next line contains a string of $N$ characters representing the yard. Each character in the string is either '.' which represents a soil cell or '#' which represents a rock cell. There are at most $50$ rock cells.
输入格式
Output in a line an integer representing the maximum number of ghosts that can be repelled per day.
输出格式
Explanation for the sample input/output #1
Let "A" be a tile of Type-1, "BB" be a tile of Type-2, and "CCC" be a tile of Type-3. The tiling "ACCCBB" in this case produces the maximum number of ghosts that can be repelled, i.e. $10 + 40 + 25 = 75$
Explanation for the sample input/output #2
This sample input has the same yard with the previous sample input, but each tile of Type-2 can repel more ghosts per day. The tiling "BB#BBA" or "BB#ABB" produces the maximum number of ghosts that can be repelled, i.e. $100 + 100 + 10 = 210$ . Observe that the third cell is left untiled.
Explanation for the sample input/output #3
The tiling "ACCCA.#", "ACCC.A#", or ".CCCAA#" produces the maximum number of ghosts that can be repelled, i.e. $30 + 100 + 30 = 160$ . Observe that there is no way to tile the last cell.
Let "A" be a tile of Type-1, "BB" be a tile of Type-2, and "CCC" be a tile of Type-3. The tiling "ACCCBB" in this case produces the maximum number of ghosts that can be repelled, i.e. $10 + 40 + 25 = 75$
Explanation for the sample input/output #2
This sample input has the same yard with the previous sample input, but each tile of Type-2 can repel more ghosts per day. The tiling "BB#BBA" or "BB#ABB" produces the maximum number of ghosts that can be repelled, i.e. $100 + 100 + 10 = 210$ . Observe that the third cell is left untiled.
Explanation for the sample input/output #3
The tiling "ACCCA.#", "ACCC.A#", or ".CCCAA#" produces the maximum number of ghosts that can be repelled, i.e. $30 + 100 + 30 = 160$ . Observe that there is no way to tile the last cell.
输入输出样例
输入 #1
6 4 10 25 40 ..#...
输出 #1
75
输入 #2
6 4 10 100 40 ..#...
输出 #2
210
输入 #3
7 2 30 10 100 ..#...#
输出 #3
160
说明/提示
Explanation for the sample input/output #1
Let "A" be a tile of Type-1, "BB" be a tile of Type-2, and "CCC" be a tile of Type-3. The tiling "ACCCBB" in this case produces the maximum number of ghosts that can be repelled, i.e. $10 + 40 + 25 = 75$
Explanation for the sample input/output #2
This sample input has the same yard with the previous sample input, but each tile of Type-2 can repel more ghosts per day. The tiling "BB#BBA" or "BB#ABB" produces the maximum number of ghosts that can be repelled, i.e. $100 + 100 + 10 = 210$ . Observe that the third cell is left untiled.
Explanation for the sample input/output #3
The tiling "ACCCA.#", "ACCC.A#", or ".CCCAA#" produces the maximum number of ghosts that can be repelled, i.e. $30 + 100 + 30 = 160$ . Observe that there is no way to tile the last cell.
Let "A" be a tile of Type-1, "BB" be a tile of Type-2, and "CCC" be a tile of Type-3. The tiling "ACCCBB" in this case produces the maximum number of ghosts that can be repelled, i.e. $10 + 40 + 25 = 75$
Explanation for the sample input/output #2
This sample input has the same yard with the previous sample input, but each tile of Type-2 can repel more ghosts per day. The tiling "BB#BBA" or "BB#ABB" produces the maximum number of ghosts that can be repelled, i.e. $100 + 100 + 10 = 210$ . Observe that the third cell is left untiled.
Explanation for the sample input/output #3
The tiling "ACCCA.#", "ACCC.A#", or ".CCCAA#" produces the maximum number of ghosts that can be repelled, i.e. $30 + 100 + 30 = 160$ . Observe that there is no way to tile the last cell.