Pro.ID21663 TitleBrick by Brick Game Title链接http://10.20.2.8/oj/exercise/problem?problem_id=21663 AC0 Submit0 Ratio- 时间&空间限制描述Brick by Brick Game is a kind of creative building game. Like all toy bricks games, it uses a set of bricks to construct buildings. In this problem, we consider a set of bricks which forms a building in rectangle shape. Our task is to remove K bricks from the building. In order to make the remaining part of the building keep standing, the following rules should be obeyed: (1) Each floor of the building (remaining part) consists of a single connected row of bricks. (2) At least one brick from each floor must rest upon some brick from the floor below it. The only exception is the bottom floor, which rest upon ground. (3) At least one brick of the bottom floor must be left. Each brick has its own visual value (a non-negative integer printed on the surface). We want to maximize the sum of the visual values on the bricks left. Can you tell me what the sum could be? For detail, Figure 1 illustrated the case in the sample input. The maximized solution follows all of the above rules. Remember that, there's no restriction on how many floors that the remaining part of the building must keep, so we may abandon some top floors.
original building visual value maximized solution Figure 1 Example 输入The first line of the input contains a positive integer T ≤ 20 specifying the number of test cases to follow. The first line of each case contains three integers: N, M and K. ( 0 < N, M ≤ 64 , And max(NM-64, 0) ≤ K < NM ) Next follow N lines, each with K integers specifying the visual values of each bricks. The first line describes the top floor of the building while the last line describes the bottom floor. All of the visual values are non-negative integers smaller than 32768. Numbers are separated by spaces. 输出Description Brick by Brick Game is a kind of creative building game. Like all toy bricks games, it uses a set of bricks to construct buildings. In this problem, we consider a set of bricks which forms a building in rectangle shape. Our task is to remove K bricks from the building. In order to make the remaining part of the building keep standing, the following rules should be obeyed: (1) Each floor of the building (remaining part) consists of a single connected row of bricks. (2) At least one brick from each floor must rest upon some brick from the floor below it. The only exception is the bottom floor, which rest upon ground. (3) At least one brick of the bottom floor must be left. Each brick has its own visual value (a non-negative integer printed on the surface). We want to maximize the sum of the visual values on the bricks left. Can you tell me what the sum could be? For detail, Figure 1 illustrated the case in the sample input. The maximized solution follows all of the above rules. Remember that, there's no restriction on how many floors that the remaining part of the building must keep, so we may abandon some top floors.
original building visual value maximized solution Figure 1 Example Input The first line of the input contains a positive integer T ≤ 20 specifying the number of test cases to follow. The first line of each case contains three integers: N, M and K. ( 0 < N, M ≤ 64 , And max(NM-64, 0) ≤ K < NM ) Next follow N lines, each with K integers specifying the visual values of each bricks. The first line describes the top floor of the building while the last line describes the bottom floor. All of the visual values are non-negative integers smaller than 32768. Numbers are separated by spaces. Output For each test case you should output a single line containing "Case X: Y" (quotes for clarity) where X is the number of the test case (starting at 1) and Y is the total visual value of the maximized solution. Sample Input 1 Sample Output Case 1: 118 Source 样例输入1 样例输出Case 1: 118 作者 |
|Archiver|手机版|小黑屋|同和创作矩阵
( 粤ICP备20019636号-1 )
GMT+8, 2025-2-3 15:17 , Processed in 0.029148 second(s), 14 queries .
Powered by Discuz! X3.4 Licensed
© 2001-2017 Comsenz Inc.
