Problem Statement
|
| |
You
have a rectangular piece of paper that's divided into 1x1 cells, each
of which has an integer value. The paper will be described by a vector
<string> paper. The ith element of paper will be a space delimited list of integers, where the jth integer of the ith element of paper represents the value of the jth cell of the ith row of the paper.
You want to perform a sequence of folds on the paper, where you may
fold anywhere along an axis that is in between two rows or columns of
the paper. After performing a fold, we wish to model the folded paper
as a new, flat piece of paper. We will do this by considering two
overlapping cells as a single cell, with a value that is the sum of the
individual cells.
You wish to perform a sequence of folds such that the value of some
single cell in the resulting piece of paper is as large as possible.
Return this value. |
Definition
|
| |
| Class: |
FoldThePaper |
| Method: |
getValue |
| Parameters: |
vector <string> |
| Returns: |
int |
| Method signature: |
int getValue(vector <string> paper) |
| (be sure your method is public) |
|
| |
|
Constraints
|
| - |
paper will contain between 1 and 12 elements, inclusive. |
| - |
Each element of paper will be a single-space delimited list of integers with no leading or trailing spaces. |
| - |
Each element of paper will contain between 1 and 12 integers, inclusive. |
| - |
Each element of paper will contain the same number of integers. |
| - |
Each element of paper will contain between 1 and 50 characters, inclusive. |
| - |
Each integer in paper will be between -100 and 100, inclusive. |
| - |
Each integer in paper will have no leading zeros. |
| - |
An integer in paper equal to zero will not have a preceding negative sign. |
Examples
|
| 0) |
|
| |
|
|
Returns: 6
|
| We can collapse every cell onto the upper-left cell. |
|
|
| 1) |
|
| |
|
|
Returns: 2
|
| We should perform only the fold between the two rows, and take the resulting left column. |
|
|
| 2) |
|
| |
{
"1 -1 -1 1",
"-1 -1 -1 -1",
"-1 -1 -1 -1",
"1 -1 -1 1"
}
|
|
Returns: 4
|
| Folding between the middle rows then the middle columns allows us to combine the four corner cells. |
|
|
| 3) |
|
| |
{
"20 13 -2 100",
"-12 0 4 -3",
"4 1 -36 21"
}
|
|
Returns: 131
|
|
|
|
| 4) |
|
| |
|
This
problem statement is the exclusive and proprietary property of
TopCoder, Inc. Any unauthorized use or reproduction of this information
without the prior written consent of TopCoder, Inc. is strictly
prohibited. (c)2003, TopCoder, Inc. All rights reserved.
題目大意是有一個(gè)12*12的矩陣，現(xiàn)在可以對(duì)這個(gè)矩陣橫向或縱向折疊，出在重疊位置的數(shù)相加。
求折疊過程中任意位置產(chǎn)生的最大數(shù)。
很多大牛fail了，我一個(gè)DFS+剪枝也超時(shí)了，一共32人pass sys test，1000pts無人ac，此套題難度還是很大的。
基本思路是狀態(tài)壓縮DP，橫向(1<<12)*縱向(1<<12)*加和。
但是這樣會(huì)超時(shí)。關(guān)鍵是沒有利用到折疊的信息。
預(yù)先生成某個(gè)位置的狀態(tài)（由那些位置疊加而來），就可以減少檢查量，就可以ac了。
如何生成這些狀態(tài)呢？沒錯(cuò)，又是一個(gè)DP. 呵呵。