SRM444DIV1 550分
大概意思是给定一个一定长宽的表,现在手中有两种卡片一种是2*2的“4”字卡片(16分),另一种是1*1的“1”字卡片(1分),卡片数不限,计算可以将其填入表中得到的最大分,图表中可能已有卡片存在。
*Problem Statement
NOTE: This problem statement contains images that may not display properly if viewed outside of the applet.
"4Blocks" is a two player cooperative game played on a special board. The board is a grid composed of 1x1 square cells. There are two different kinds of blocks: '1' blocks and '4' blocks. '1' blocks are 1x1, and '4' blocks are 2x2:
You must place blocks on the board so that their sides are aligned to the grid lines and no two blocks overlap. The final score is the sum of the values in each cell. '1' blocks are worth 1 point, and '4' blocks are worth 16 points because they cover 4 cells and each cell is worth 4 points.
Your friend has taken his turn and placed a number of '1' blocks on the board. The current configuration is given in the String[] grid. The j-th character of the i-th element of grid is '.' if the cell at row i, column j is empty, and '1' if your friend placed a '1' block in that cell. It is now your turn, and you can place any number of '1' or '4' blocks on the board, but you cannot remove any of the blocks that have already been placed. Return the maximum score that can be achieved. For example, the following images show one possible starting state, and the optimal placement of blocks from that state:
The final score would be 4*16 + 6*1 = 70.
Definition
Class: FourBlocks
Method: maxScore
Parameters: String[]
Returns: int
Method signature: int maxScore(String[] grid)
(be sure your method is public)
Constraints
- grid will contain between 1 and 10 elements, inclusive.
- Each element of grid will contain between 1 and 25 characters, inclusive.
- All elements of grid will contain the same number of characters.
- Each element of grid will contain only '.' or '1' (one).
Examples
0)
{".....1..1..",
"..1.....1.."}
Returns: 70
This is the example from the statement.
1)
{"...1.",
".....",
".1..1",
".....",
"1...."}
Returns: 73
2)
{"...1.",
".1...",
"..1.1",
"1...."}
Returns: 20
It is not possible to place any '4' bricks in this setup.
3)
{".....1...",
".....1...",
"111111111",
".....1...",
".....1..."}
Returns: 117
发现最做Topcoder有个老是习惯先浏览一下其他人的算法,大概心里有数。这道题刚开始看时确实有点吓到,列位大牛写的东西几乎看不懂,还用到了位运算,有的就用三维数组,真是云里雾里。
不过自己尝试一下发现不是那么回事,一气写下来就调了一个bug,算了一下复杂度照其他来说还是比较低的。
可见有时候还是应该相信自己多一点。算法如下:
相关推荐
这个是用来制作课件时常用的程序代码,authware填图游戏程序
来自互联网的小软件。 孩子们会满意。 balilarning zihnini achidighan oyun ditali
世界地图填图
亚洲填图训练带答案.pdf
初中地理系统填图.pdf
辛苦整理的数字填图标准以及用色标准 希望有帮助
CAD在地质填图中的应用.pdf
湘教版七年级地理(下册)填图练习.doc
(完整word版)世界地图的填图练习
数字填图,野外操作系统,andriod系统手机操作软件。
1_25万遥感地质填图方法和技术.part4 好东西
数字填图系统在区调修测中的应用技巧,祝艳,柳长峰,国内数字地质填图技术在区域地质调查工作中已经得到了广泛的应用,取得了很大进步,同时也突出了一些实际的问题。本文通过内蒙古
主要是关于地质填图技术方面的架构资料和详细的技术方案,有利于相关从业人员阅读学习。
三年级奥数找规律填图PPT教案.pptx
MapGIS 10三维地质填图工具使用手册
数字填图是将你一天区调工作的成果通过掌上机反映到电脑上的系统
概述了导航型GPS接收机的工作原理和求解坐标...在实际测量作业中,采取直接用导航型GPS测定已知公共点X、Y、Z值求解坐标转换参数的方法,从而降低了单点绝对定位的误差,达到了1∶10000比例尺地质填图定位测量的精度要求。
七下地理填图复习题集(含答案解析).doc
新型人工智能矿物填图技术将助力提高矿山运营效率和保障人员安全.pdf
小游戏源码-古埃及对称填图智商测试,太邪门了.rar