[USACO][Section 1.4][模拟] Packing Rectangles

前言：

这是一道令人望而却步的题，没有什么技术难度却又很需要勇气。解决它所需要花费的时间实际并不长，但就是怕麻烦的这种心理障碍让我迟迟无法下手，真需要好好反省一下。

题目大意：

给出4个矩形的长宽，求能包含4个矩形的最小矩形的面积，并输出其长宽。

思路：

题目通过图片形式给出了6种基本组合方式（4、5其实是一种），只需要把4个矩形插入相应位置即可。通过全排列遍历所有插入方案，再通过四重循环遍历所有翻转方案（横放或竖放）。简单计算下：需要遍历一共5*4!*2^4个方案后才能确定最终答案。

代码：

/*
ID: lujunda1
LANG: C++
PROG: packrec
*/
#include
#include
#include
#include
using namespace std;
int rect[4][2];
//rectangle 用于存储4个矩形的长宽，rect[i][0]表示第i个矩形的长度，rect[i][1]表示其宽度。 
int order[4]={0,1,2,3};
//顺序数组，每个基本排列中，交换矩形的位置。共有24种组合。 
int tmp[4][2];
//存储通过顺序处理和翻转处理后的矩形信息。 
int t[4];
//t[i]为1时，表示第i个矩形需要翻转90°，为0时不需要翻转。 
int min_size=1000000;
//表示最小面积 。 
int total;
//表示最小面积包含的方案数量。 
map mark;
struct result
{
    int length;
    int width;
}res[100];
//存储最小面积包含的所有方案。 
int max(int a,int b)
{
    return a>b?a:b;
}
int max(int a,int b,int c)
{
    return max(max(a,b),c);
}
int max(int a,int b,int c,int d)
{
    return max(max(a,b,c),d);
}
int cmp(const void* m,const void* n)
{
    return (*(result*)m).width-(*(result*)n).width;
}
void change()
//根据order[]和t[]来生成tmp[]。 
{
    for(int i=0;i<4;i++)
        for(int j=0;j<=1;j++)
            tmp[i][j]=rect[order[i]][j];
    //顺序处理 
    for(int i=0;i<4;i++)
        if(t[i])
            swap(tmp[i][0],tmp[i][1]);
    //翻转处理 
}
void updata(int length,int width)
//根据当前大矩形长宽来更新res[]。 
{
    if(length

发表回复取消回复