题解 P1212 【铺放矩形块】

· · 题解

首先，这是一道很简单很麻烦的模拟题，具体摆放方式题目已经给出了，于是就根据题目来写就好了;

其次，看见前面的dalao使用for循环找排列，我用了dfs的方式(苣蒻标配);

放代码(代码里标了一些容易出错的地方以及解释，大概能看懂吧...)

#include<bits/stdc++.h>
using namespace std;

int x[5],y[5],ans=10000,tot,tmpx[5],tmpy[5];
bool vis[5],c[1005];

void alter(int x,int y)
{
    if(x*y<ans)//更新值
    {
        ans=x*y;
        memset(c,0,sizeof(c));
    }
    if(x*y==ans) c[x]=c[y]=1;
}

void check()//x表示宽//就是横着的线，y表示高//就是竖着的线咯;
{
    int x,y;
    /*
        编号顺序：
        1 2 3 4
        1 2 3 4
    */
    x=tmpx[1]+tmpx[2]+tmpx[3]+tmpx[4];
    y=max(max(tmpy[1],tmpy[2]),max(tmpy[3],tmpy[4]));
    alter(x,y);
    /*
        编号顺序：
        1 2 3
        4 4 4
    */
    x=max(tmpx[1]+tmpx[2]+tmpx[3],tmpx[4]);
    y=max(tmpy[1],max(tmpy[2],tmpy[3]))+tmpy[4];
    alter(x,y);
    /*
        编号顺序：
        1 2 4
        3 3 4
    */
    x=max(tmpx[1]+tmpx[2],tmpx[3])+tmpx[4];
    y=max(max(tmpy[1],tmpy[2])+tmpy[3],tmpy[4]);
    alter(x,y);
    /*
        编号顺序：//然后发现4,5种情况没有什么实质性的差别，于是合并它们;
        1 2 4
        1 3 4
    */
    x=tmpx[1]+max(tmpx[2],tmpx[3])+tmpx[4];
    y=max(tmpy[1],max(tmpy[2]+tmpy[3],tmpy[4]));
    alter(x,y);
    /*将矩形按照如下编号：
        1 2
        3 4
      然后?...然后自己画图分析吧
    */
    y=max(tmpy[1]+tmpy[3],tmpy[2]+tmpy[4]);
    if(tmpy[1]+tmpy[3]<=tmpy[4])    x=max(tmpx[2],max(tmpx[1],tmpx[3])+tmpx[4]);
    else if(tmpy[3]<=tmpy[4]&&tmpy[1]+tmpy[3]>=tmpy[4]) x=max(tmpx[1]+tmpx[2],max(tmpx[1],tmpx[3])+tmpx[4]);
         else if(tmpy[3]>=tmpy[4]&&tmpy[3]<=tmpy[2]+tmpy[4]) x=max(tmpx[1]+tmpx[2],max(tmpx[2],tmpx[4])+tmpx[3]);
              else if(tmpy[3]>=tmpy[2]+tmpy[4]) x=max(tmpx[1],max(tmpx[2],tmpx[4])+tmpx[3]);
    alter(x,y);//恩，注意考虑等于号的临界状态;
}

void dfs(int yj)//dfs生成排列
{
    if(yj==4)
    {
        check();return ;
    }
    for(int i=1;i<5;i++)
        if(!vis[i])
        {
            tmpx[yj+1]=x[i],tmpy[yj+1]=y[i],vis[i]=1;
            dfs(yj+1);
            tmpx[yj+1]=y[i],tmpy[yj+1]=x[i];
            dfs(yj+1);
            vis[i]=tmpx[yj+1]=tmpy[yj+1]=0;
        }
}

int main(){
    for(int i=1;i<5;i++) scanf("%d%d",&x[i],&y[i]);
    dfs(0);
    printf("%d\n",ans);
    for(int i=1;i<=sqrt(ans);i++)
        if(c[i]) printf("%d %d\n",i,ans/i);
    return 0;
}

附：编号排序是我对矩形编的号，有助于代码理解;