oyjpArt ACM/ICPC算法程序设计空间

// I am new in programming, welcome to my blog
I am oyjpart(alpc12, 四城)
posts - 224, comments - 694, trackbacks - 0, articles - 6

SRM406 PTS500 FoldThePaper

Posted on 2008-06-18 11:29 oyjpart 阅读(1520) 评论(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)
    
{
"1 1 1",
"1 1 1"
}
Returns: 6
We can collapse every cell onto the upper-left cell.
1)
    
{
"1 -1",
"1 -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)
    
{
"0"
}
Returns: 0

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. 呵呵。



只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理