跳至正文

Packing Rectangles 铺放矩形块 (IOI 95)

Packing Rectangles 铺放矩形块 (IOI 95)

在网上看了挺多解释这一题的文章,总感觉没看大懂,所以自己写一篇文章吧。希望能够帮助大家理解一下这一题。题目如下:

http://www.nocow.cn/index.php/Translate:USACO/packrec

开始拿到题目确实没怎么看懂,网上也有很多人说它是个水题,我倒感觉不以为然,我看了一些网上的人写的代码,说它是水题的人都是怎么写的。整个程序框架就是第一种情况循环+判断,第二种情况循环+判断,…………(以此类推)

接下来我来说下我的做法,(我的语言表达能力却是不强,可能会看不懂,所以如果你看不懂分析的话直接看代码的注释吧。)

对于任何一个矩形都有两种数据:长和宽,然而在这个程序中这方面是最难处理的也就是如何交换长和宽,也就是说在同一个矩形会拥有两种状况——横着摆,竖着摆。我就用srch1这个函数来实现所有矩形长和宽的交换。

接下来就是位置的问题,该把哪个矩形放在哪里面积最小呢呢?当然,这个是看不出来的。所以也需要进行反复的迭代,我用srch2来实现的。

最后再就是判断6种情况(其实只有五种,4和5是一样的)。

(不知道描述清楚没有。)接下来我把代码进行一下简单的注释吧。

C语言: Codee#12439

/*
LANG: C
ID: zqy11001
PROG: packrec
QQ: 328400264
*/
#include <stdio.h>

#define swap(a, b) do{\\
 a ^= b;\\
 b ^= a;\\
 a ^= b;\\
}while(0);
#define max(a, b) ((a)>(b)?(a):(b))

int m;
int ans[300], s1[4], s2[4];
int a[4], b[4];

void update(int x, int y)
{
 if(x * y < m){
 m = x * y;
 memset(ans, 0, sizeof(ans));
 }
 if(x * y == m){
 ans[x] = ans[y] = 1;
 }
}

int box(int x1, int y1, int x2, int y2, int x3, int y3,
 int x4, int y4)
{
 int x, y;
 x = x1 + x2 + x3 + x4;
 y = max(max(y1, y2), max(y3, y4));
 update(x, y);

 x = max(x1, x2 + x3 + x4);
 y = y1 + max(y2, max(y3, y4));
 update(x, y);

 x = x1 + max(x2, x3 + x4);
 y = max(y1, y2 + max(y3, y4));
 update(x, y);

 x = x1 + x4 + max(x2, x3);
 y = max(y1, max(y4, y2 + y3));
 update(x, y);

 x = max(max(x1 + x2, x3 + x4), x1 + x4);
 y = max(max(y1 + y3, y2 + y4), y2 + y3);
 update(x, y);
}

void srch2(int n)
{
 int i;
 if(n == 4){
 box(a[s2[0]], b[s2[0]], a[s2[1]], b[s2[1]],
 a[s2[2]], b[s2[2]], a[s2[3]], b[s23]]);
 }else{
 for(i = 0; i < 4; i++){
 if(!s1[i]){
 s2[n] = i;
 s1[i] = 1;
 srch2(n + 1);
 s1[i] = 0;
 }
 }
 }
}

void srch1(int n)
{
 if(n == 4){
 memset(s1, 0, sizeof(s1));
 srch2(0);
 }else{
 srch1(n + 1);
 swap(a[n], b[n]);
 srch1(n + 1);
 swap(a[n], b[n]);
 }
}

int main(void)
{
 int i, j;
 freopen(packrec.in, r, stdin);
 freopen(packrec.out, w, stdout);
 for(i = 0; i < 4; i++){
 scanf(%d%d, &a[i], &b[i]);
 }
 m = 10000;
 srch1(0);
 j = sqrt(m);
 printf(%d\\n, m);
 for(i = 1; i <= j; i++){
 if(ans[i]){
 printf(%d %d\\n, i, m / i);
 }
 }
 return 0;
}

接下来我对函数一个个进行一下简单的分析吧。
首先

#define swap(a, b) do{\\
 a ^= b;\\
 b ^= a;\\
 a ^= b;\\
}while(0);
#define max(a, b) ((a)>(b)?(a):(b))

这两个宏是很简单的,swap把a和b交换一下位置,max是求两者最大值。

Tip: 对于swap的话,三个异或就能完成问题,这个可能部分读者看不懂,本文是对这个题目的分析,如果看不大懂的话就改成

#define swap(a, b) do{\\
 int t;\\
 t = a;
 a = b;
 b = t;
}while(0);

然后再是对变量进行分析,ans是存储结果用的,因为题目要求输出的时候要从小到大,所以使用ans来存储,输出的时候判断如果当前的值是1的话就输出,不然的话就继续寻找下一个。m是面积最大值。a和b是存储长和宽的。s1和s2到要用的时候再介绍吧。

box函数就是对六种情况算面积,再用update函数来更新m和ans两个全局变量,如果这一种情况求出的面积和m的一样,那么就用这个面积的长和宽来更新ans。如果面积比m还要小,那么将m设置成这个面积,将ans置空,再用长和宽来更新ans。

接下来先介绍srch1吧。

void srch1(int n)
{
 if(n == 4){
 memset(s1, 0, sizeof(s1));
 srch2(0);
 }else{
 srch1(n + 1);
 swap(a[n], b[n]);
 srch1(n + 1);
 swap(a[n], b[n]);
 }
}

这个n表示当前这种方案的下标。

这个函数可以这么理解,

先直接调用一次srch1(n + 1);就是枚举四个矩形用a做底,b做高的所有情况,接下来在把第n个矩形的长和高调一下位置再srch1(n + 1).因为刚刚把第n个矩形的长和高换了位置,所以还要把它换回来。

然后当n==4的时候,四个矩形都递归完了,就该做些什么了,做些什么呢?

继续看就知道了。

调用srch2之前为什么要把s1置0呢`?

看看srch2是怎么写的`

void srch2(int n)
{
 int i;
 if(n == 4){
 box(a[s2[0]], b[s2[0]], a[s2[1]], b[s2[1]],
 a[s2[2]], b[s2[2]], a[s2[3]], b[s2[3]]);
 }else{
 for(i = 0; i < 4; i++){
 if(!s1[i]){
 s2[n] = i;
 s1[i] = 1;
 srch2(n + 1);
 s1[i] = 0;
 }
 }
 }
}

可能有读者要说了,这跟srch1有点像啊.. 好吧, 我承认, 我摘抄了srch1的部分代码,但是srch2的功能未必也是将第n个矩形的长和高交换?肯定不是啦。

当n==4的时候就是真正的进行判断了,所以理解else是重点.本函数的功能是,对四个矩形的长和高调用box的时候的顺序进行反复的交换。所以else里面是一个for循环,这里s1和s2就是用来判断重复的情况的,s1标志当前这个矩形是否已经被使用了?s2标志当前这个矩形的实质是什么?

汗,,自己都没看懂这段话,再理一下。。

s2[i]的意思是第i个矩形实际上是第几个矩形。因为四个矩形要反复的进行交换,所以s2就是交换的中间变量。那有人会问了。

 if(!s1[i]){
 s2[n] = i;
 s1[i] = 1;
 srch2(n + 1);
 s1[i] = 0;
 }

这段是什么意思呢? 呵呵,你们想想,如果直接

s2[n] = i;

srch2(n + 1);

的话那会有这种可能s2[0] == 0, s2[1] == 0, s2[2]==0, 也就是说在调用box的时候这些矩形分身了。s1在这里就是用来防止这种情况,s1用来标志这一个矩形是否被别的s2给使用了,如果使用了那s1就会是1,那么循环只好继续。

整个程序大概分析完了。。

如果还没看懂,那不是你蠢了,是我没写清楚吧。

总之如果还有问题,联系我的QQ:328400264

发表回复

您的电子邮箱地址不会被公开。