Posted on 2008-06-18 11:29
oyjpart 閱讀(1554)
評論(0) 編輯 收藏 引用 所屬分類:
ACM/ICPC或其他比賽 、
程序設計
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.
題目大意是有一個12*12的矩陣，現在可以對這個矩陣橫向或縱向折疊，出在重疊位置的數相加。
求折疊過程中任意位置產生的最大數。
很多大牛fail了，我一個DFS+剪枝也超時了，一共32人pass sys test，1000pts無人ac，此套題難度還是很大的。
基本思路是狀態壓縮DP，橫向(1<<12)*縱向(1<<12)*加和。
但是這樣會超時。關鍵是沒有利用到折疊的信息。
預先生成某個位置的狀態（由那些位置疊加而來），就可以減少檢查量，就可以ac了。
如何生成這些狀態呢？沒錯，又是一個DP. 呵呵。