[Shoi2007]Bookcase 书柜的尺寸

[Shoi2007]Bookcase 书柜的尺寸

Time Limit:5000MS  Memory Limit:65536K
Total Submit:21 Accepted:7
Case Time Limit:1000MS

Description

Tom不喜欢那种一字长龙式的大书架,他只想要一个小书柜来存放他的系列工具书。Tom打算把书柜放在桌子的后面,这样需要查书的时候就可以不用起身离开 了。显然,这种书柜不能太大,Tom希望它的体积越小越好。另外,出于他的审美要求,他只想要一个三层的书柜。为了物尽其用,Tom规定每层必须至少放一 本书。现在的问题是,Tom怎么分配他的工具书,才能让木匠造出最小的书柜来呢?
Tom很快意识到这是一个数学问题。每本书都有自己的高度hi和厚度ti。我们需要求的是一个分配方案,也就是要求把所有的书分配在S1、S2和 S3三个非空集合里面的一个,不重复也不遗漏,那么,很明显,书柜正面表面积(S)的计算公式就是:

由于书柜的深度是固定的(显然,它应该等于那本最宽的书的长度),所以要求书柜的体积最小就是要求S最小。Tom离答案只有一步之遥了。不过很遗 憾,Tom并不擅长于编程,于是他邀请你来帮助他解决这个问题。

Input

文件的第一行只有一个整数n(3≤n≤70),代表书本的本数。接下来有n行,每行有两个整数hi和ti,代表每本书的高度和厚度,我们保证 150≤hi≤300,5≤ti≤30。

Output

只有一行,即输出最小的S。

Sample Input

4
220 29
195 20
200 9
180 30

Sample Output

18000

Source

Day2

哎。。回到正常状态了。。开始写解题报告>_<。。。
反正我现在感觉题目神马做多少都是浮云。。。也就那么几个核心思想>_<。。
首先这题自然要dp。。暴力dp记录每层显然不可能>_<。。dp自然需要一个序。。宽度显然不能为我们提供序>_<。。因为对于宽度的操作是和。。而和这玩意是对称的。。。
所以要找一个序。。。
1)Dp要有序。。。寻找序。。
2)神马是序呢。。一般来说是要先决定最重要的>_<。。而高度大的显然比较重要,所以按高度排序。。
那么状态就出来了。。Dp[i][w1][w2]表示前i个柜子,第一个层宽度和w1,第二个层宽度和w2。。
那么第三个层的宽度和也就是可以算出来。。
表示神马呢?表示三层每层最大值的最小和。
考虑第i个放入w1。。如果w1为0。那么由于后面的都比现在的小,第一层最大值就是第i个的高度。。
如果w1不为0.那么对最大值就没有影响。。
就可以做了>_<。。常数要优化一下。。。

3 thoughts on “[Shoi2007]Bookcase 书柜的尺寸

  1. “题目神马做多少都是浮云。。。也就那么几个核心思想”ORZ!!!!!!!神犇一眼就看出了OI的本质,太强了!!!!!!!!

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>