USACO/packrec

来自NOCOW

< USACO

跳转到：导航, 搜索

[编辑] 分析

只要将示例中的6种(其实是5种,图4和5是同一种情况)进行模拟,以求得最优解

最开始觉得完全无法下手（因为如果通过建立坐标系来枚举的话是绝对会超时的）。

最后发现这题目太阴了。（实际上也是自己的水平不够）

注意题中那副图，下面有一排小字：

"The six basic layouts of four rectangles"

注意了，这里面并没有"possible"一词，也就是说图上描绘的就是所有的basic layouts。

仔细想想确实也必须这样啊！basic layouts到底有几种，分别是什么样，这是一个数学本身要解决的问题，对于仅仅是应用数学的计算机科学来说，这个并不是它所关注的问题，数学家已经为我们提供了理论基础，我们只需要通过这些已经建立的模型进行计算就行了。

既然已经知道了所有可能的摆放方式，接下来的问题就简单了(思维上)。

对某个确定的摆放模型来说，都有且只有4个位置可以选择。

我们只需要搜索出4个矩形的全排列，将其填入对应位置，然后分别用6种模型进行计算即可。

这用dfs实在是太容易做到了。

还有需要注意的地方是，题目对输出结果格式的要求，我没有找到自动排成规定的格式的方法，所以是在搜索完成后再对答案进行整理(这里又需要排序),最后输出结果的。

由于矩形的个数是确定的4个，所以dfs需要的时间大约为4!=24，完全可以接受。

从上面的分析可以看出，编码量是巨大的，我采用的一个减少编码量的技巧是使用函数指针数组来表示6种计算模型。

最后，其实最后两种模型是可以合并为一种的，不过多一种又有什么关系呢？

——By Aikilis

一些小提示：

1、痛恨背诵快排？那就写一个布尔数组的基数排序，然后最后输出的时候只需要检查最小的面积的根号就行了。

最劣情况是4个边长50的正方形排成一排，数组开到200即可。

2、第4、5种情况明显可以合并

3、1~5种不用考虑面积重叠，样例给的图么，所见即所得，直接写算式即可。

但是第6种就要注意重叠问题了。

提示性思路：

警告：以下思路未经过严谨验证，只保证过USACO提供的21个样例

规定一下使用的变量：

maxx，maxy：拼接好后封闭矩形横向长度和纵向长度

save[1..4,1..2]存放第i个矩形的横向和纵向长度，比如第2个矩形的横向长度为save[2,1]，纵向长度为save[2,2]

首先，放置的方法是4个角各一个矩形。

那先给矩形标号：

1 3

2 4

然后直接看题目描述中给的图，可以发现满足下面的式子：

maxx:=max(save[1,1]+save[3,1],save[2,1]+save[4,1]);

maxy:=max(save[1,2]+save[2,2],save[3,2]+save[4,2]);

然后第6种情况先这么写着，然后用样例测试一下，发现不对，只有36.

然后让程序输出找到的最小解的矩形的摆法，依次输出了

((1,2),(3,4),(5,4),(3,2))

（格式：(矩形1的横向长度，矩形1的纵向长度)，......）

你把输出的这个带回到分析出的式子，发现矩形被摆成了这个样子：

矩形发生重叠了，如何取消掉重叠？两种思路：

1、不进行横向移动，只进行纵向移动

2、不进行纵向移动，只进行横向移动

两种思路取1即可。我们这里采取思路1.

思路1的话，把3号方块向上移动就可以解决问题了。

3号方块向上移动，意味着我们对横向长度的计算不需要重新编写，纵向长度需要重新考虑。

于是让我们改写成这样：

maxy:=max(save[1,2],save[3,2])+max(save[2,2],save[4,2]);

但是，这样的式子不适合题目描述中所给的图的情况，所以还需要想想如何判断来决定什么时候用什么样的式子。

为什么会出现矩形纵向移动的需要？因为矩形3要叠放在矩形2上面，而不是我们一开始看到的叠放在了矩形4上面，才会不重叠。

如何用表达式描述矩形3要叠放在矩形2上面？

(save[2,2]>save[4,2])and(save[3,1]>save[4,1])——2号比4号高，4号横向没3号胖

不要以为完工了，把图形上下翻转（1、2对调，3、4对调），并做一次自由落体

如果采用一开始那个式子，又会出现重叠现象，需要把1号方块向上移动。

这时候，1号方块要叠放在4号方块之上，而不是2号方块之上。

如何表述？——

(save[1,1]>save[2,1])and(save[4,2]>save[2,2])——1号比2号横向要胖，4号比2号要高

然后，两种情况，出现任何一种都要用后面分析出来的式子。

合并一下：

 if (((save[1,1]>save[2,1])and(save[4,2]>save[2,2]))or((save[2,2]>save[4,2])and(save[3,1]>save[4,1]))) then 
      maxy:=max(save[1,2],save[3,2])+max(save[2,2],save[4,2])
 else maxy:=max(save[1,2]+save[2,2],save[3,2]+save[4,2]);

这就是第六种情况的纵向计算的完整写法。

该方法实现的代码见C++ skyxxzc Pascal fcxxzux1

接下来介绍本人（本人是从上面那条线开始写起的）的处理第6种的方法。

应该比楼上的简单而且本人过了。（说实在我没看懂楼上的）

以样例4 3 4 4 6 3 5 5说明

进行4!（位置）*2^4（每个的横竖）次搜索，

想法是将四块摆放如下

1 3

2 4

并将靠中间的四个角对齐，这个例子中是这样的：

当然只是想想，不用代码

0 0 0 0 0 3 3 3

1 1 1 1 1 3 3 3

0 2 2 2 2 4 4 4 4

0 2 2 2 2

然后把较高的右边这条向下移动一格使各块都靠最底（有些例子是左边或者不移动）：

此时计算整体图形的高max(1高+2高,3高+4高)因为接下来要水平移动，不会使高减少

1 1 1 1 1 3 3 3

0 2 2 2 2 3 3 3

0 2 2 2 2 4 4 4 4

然后将2 和4 向左移至与1 对齐（将1 和3 向右移是一样的）：

需要提前验证是否可以向左移动（满足 2高>=4高）

以及移动是否能缩小宽度（(1宽>2宽)or(3宽<4宽)）不然移动没有意义

移动之后，整体图形的宽为max(1宽+3宽,2宽+4宽)

如果不移动整体图形的宽为max(1宽,2宽)+max(3宽+4宽)

1 1 1 1 1 3 3 3

2 2 2 2 0 3 3 3

2 2 2 2 4 4 4 4

移动完就好了

其实说了这么多代码只有3行：

整体图形的高:=max(1高+2高,3高+4高)

if(2高>=4高)and((1宽>2宽)or(3宽<4宽))then整体图形的宽:=max(1宽+3宽,2宽+4宽)

else整体图形的宽:=max(1宽,2宽)+max(3宽+4宽)

以下是我用pascal写的

  h:=da(l[i1,j1]+l[i2,j2],l[i3,j3]+l[i4,j4]);
  if (l[i2,j2]>=l[i4,j4])and((l[i1,3-j1]>l[i2,3-j2])or(l[i3,3-j3]<l[i4,3-j4]))
    then w:=da(l[i1,3-j1]+l[i3,3-j3],l[i2,3-j2]+l[i4,3-j4])
    else w:=da(l[i1,3-j1],l[i2,3-j2])+da(l[i3,3-j3],l[i4,3-j4]);

代码很短。。。60多行。不过我不知道怎么发代码

ycxx_fx1

表示看不懂楼上的和楼上的楼上的，我说一下我想法

先把四个长方形编号0,1,2,3

这样摆：

0 1

2 3

那么，对于0和3的相对位置，有两种

一种是（方式一）

0 0 0 -

- 3 3 3

此时record.x=max(rec[0].x+rec[1].x,rec[2].x+rec[3].x);

一种是（方式二）

0 0 0 - - -

0 0 0 3 3 3

- - - 3 3 3

此时record.x=max(max(rec[0].x+rec[1].x,rec[2].x+rec[3].x),rec[0].x+rec[3].x);

对于1和2，也是一样。

但是，如果都按（方式一）摆，会出现重叠，那么这种情况就可以删去了，因为此时无论如何按照楼上提供平移方法都不会得到最优解（可证，略）所以就搞定了

21个数据全过

[编辑] 参考代码

C
C++
Pascal
Java

[编辑] 引用

[1]

[2]

USACO/packrec

[编辑] 分析

[编辑] 参考代码

[编辑] 引用

查看

个人工具

导航

搜索

工具箱