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