Posted on 2008-06-18 11:29
oyjpart 阅读(1539)
评论(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. 呵呵。