【USACO】铺放矩形块

问题描述

　　给定4个矩形块，找出一个最小的封闭矩形将这4个矩形块放入，但不得相互重叠。所谓最小矩形指该矩形面积最小。
　　所有4个矩形块的边都与封闭矩形的边相平行，图1示出了铺放4个矩形块的6种方案。这6种方案仅只是可能的基本铺放方案。因为其它方案能由基本方案通过旋转和镜像反射得到。
　　可能存在满足条件且有着同样面积的各种不同的封闭矩形，你应该输出所有这些封闭矩形的边长。

输入格式

　　共有4行。每一行用两个正整数来表示一个给定的矩形块的两个边长。矩形块的每条边的边长范围最小是1，最大是50。

输出格式

　　总行数为解的总数加1。第一行是一个整数，代表封闭矩形的最小面积（子任务A）。接下来的每一行都表示一个解，由数P和数Q来表示，并且P≤Q（子任务B）。这些行必须根据P的大小按升序排列，P小的行在前，大的在后。且所有行都应是不同的。

解题算法

【模拟】

解题历程：

初看无思路

情况极多如乱麻

觉得用函数实现可能比较快

代码：

if(cnt==4)
   {
       if(x*y<sum)
       {
           memset(vis,0,sizeof(vis));
           sum=x*y;
           ans[ans[0]=1]=min(x,y);
           vis[min(x,y)]=1;
       }
       else if(x*y==sum&&!vis[min(x,y)])
       {
           ans[++ans[0]]=min(x,y);
           vis[min(x,y)]=1;
       }
   }
   else
   F(i,0,3)
   if(!vit[i])
   {
       vit[i]=1;
       //1
       int xx=x+ex[i];
       int yy=max(y,ey[i]);
       dfs(xx,yy,cnt+1);
       //2
       xx=x+ey[i];
       yy=max(y,ex[i]);
       dfs(xx,yy,cnt+1);
       //3
       xx=max(x,ex[i]);
       yy=y+ey[i];
       dfs(xx,yy,cnt+1);
       //4
       xx=max(x,ey[i]);
       yy=y+ex[i];
       dfs(xx,yy,cnt+1);
       vit[i]=0;
   }

以上、

WA61

预料了...因为可以嵌进去的情况未考虑

所以分数很可观

然后无思路

瞎搞

代码：

num[0]=1;
   F(i,1,6)
   {
   if(i<3)num[1]=2;
   else if(i<5)num[1]=3;
   else num[1]=4;
   if(i==1||i==6)num[2]=3;
   else if(i==2||i==4)num[2]=4;
   else num[2]=2;
   if(i==1||i==3)num[3]=4;
   else if(i==2||i==5)num[3]=3;
   else num[3]=2;
   if(ex[num[0]]<=ey[num[1]]&&ex[num[1]]<=ey[num[2]]&&ey[num[3]]+ex[num[0]]<=ey[num[1]]+ex[num[2]])
   {
       int x=ex[num[2]]+ey[num[1]];
       int y=max(ex[num[1]]+ey[num[0]],ey[num[2]]+ex[num[3]]);
       if(x*y<sum)
       {
           memset(vis,0,sizeof(vis));
           sum=x*y;
           ans[ans[0]=1]=min(x,y);
           vis[min(x,y)]=1;
       }
       else if(x*y==sum&&!vis[min(x,y)])
       {
           ans[++ans[0]]=min(x,y);
           vis[min(x,y)]=1;
       }
   }
}

以上、

WA53

很明显是错的...水分也没水到

所以目前无思路

以上

2018.2.14

-----------------------------------------------------------------------

一个寒假之后

我回来了。。。

并且用了半个小时做了出来（上网看了看题解发现比我的还烦kkk）

思路重启：

之前处理无嵌入部分的做法当然是标准解

对于嵌入情况仔细想了想

可以只针对一个方向的嵌套而言

因为其他方向的嵌套可以通过方块的转移来实现

如图：

这里想要嵌入发现一个限制条件：

黄块底边要小于蓝块

黄块高边要低于绿块

这样能清晰看出结果

x=max(ex[黄]+ex[绿],ex[蓝]+ex[红]);

y=max(ey[黄]+ey[蓝],ey[绿]+ey[红]);

然后子程序枚举所有情况

很简单

代码：

void do_spe()
{
   if(side[4]<3)
   {
       F(i,0,3)
   if(!vit[i])
   {
       side[++side[4]]=i;
       vit[i]=1;
       do_spe();
       exchange(&ex[i],&ey[i]);
       do_spe();
       exchange(&ex[i],&ey[i]);
       vit[i]=0;
       side[4]--;
   }
   }
   else
   {
       if(!(ey[side[0]]<=ey[side[1]]&&ex[side[2]]<=ex[side[0]]))return;
       int xx=max(ex[side[2]]+ex[side[3]],ex[side[1]]+ex[side[0]]);
       int yy=max(ey[side[0]]+ey[side[2]],ey[side[1]]+ey[side[3]]);
       //cout<<xx<<" "<<yy<<endl;
       if(xx*yy<sum)
       {
           F(i,0,3)
           //cout<<ex[side[i]]<<" "<<ey[side[i]]<<endl;
           memset(vis,0,sizeof(vis));
           sum=xx*yy;
           ans[ans[0]=1]=min(xx,yy);
           vis[min(xx,yy)]=1;
       }
       else if(xx*yy==sum&&!vis[min(xx,yy)])
       {
           ans[++ans[0]]=min(xx,yy);
           vis[min(xx,yy)]=1;
       }
   }
   return;
}

以上

模拟专题over

以上

2018.3.4