P5917

2021CHD · 2025-01-08 20:21:52 · 题解

前言

不用分类讨论。

其实不知道为什么 P1212 和 P5917 两题现有的 12+5=13 篇题解都是分六类（或五类）讨论做的。（可能和 P1212 题面上的那几幅图有关）

但是其实可以不用的，有一种丝毫不用分类讨论而且可以拓展到任意数量矩形的做法。

题意

给定 n=4 个矩形，可以任意旋转平移，要求矩形之间不可以相互重叠，并且矩形的边必须与坐标轴平行，求面积最小的可以容纳给定矩形的矩形的面积和形状，矩形边长不超过 V=50。

思路

首先可以先想最优的矩形排列会长成什么样，给一张图：

这个解看起来是最优的。（实际上也是）

那么这个解有什么特点呢？

每个矩形都尽可能地向左下角靠拢。

容易说明，如果一个矩形可以向左下方移动，那这个矩形移动以后这个解不会更劣，如果这个解已经是最优解，那这样做不会影响到这个解的形状，所以只需要统计每个矩形都尽可能地向左下角靠拢的情况就足以求出正确答案。

所以，可以考虑枚举矩形放置的顺序和每个矩形是否旋转 90^{\circ}，然后按顺序放置矩形，并保证所有矩形不能向左下方移动的方案都被枚举到。

具体地，如果矩形不能向左下方移动，那它的左边界一定紧贴某个矩形的右边界或者紧贴最左边，它的下边界一定紧贴某个矩形的上边界或者紧贴最下边。所以可以考虑枚举一个矩形的左边界在哪里，然后找到最靠下的一个下边界使得这个矩形的放置合法，然后尝试将这个矩形放在这个位置。

注意这样做只保证了矩形不能向下方移动，而没有保证矩形不能向左方移动，但是所有矩形不能向左下方移动的可能性都会被枚举到，所以这样做是可行的。

有一个小优化：第一个放置的矩形一定可以不旋转 90^{\circ}，因为只要把整个局面沿 y=x 翻转就可以达到同样的效果，不过在这题的数据范围下是没有必要的。

然后就做完了，有什么细节问题可以看看代码，时间复杂度是 O\left((n!)^22^nn^2+nV\right)，空间复杂度是 O(nV)。

最后贴上 AC 记录和代码。

#include<cstdio>
#include<cstdlib>
using namespace std;
const int n=4;
int x[10],y[10],i,j,pl[10],bj[10],rev[10],l[10],r[10],d[10],u[10],ans=100000000,wans[1000],tt[1000],top;
int min(int a,int b)
{
    if(a<b)
    return a;
    else
    return b;
}
int max(int a,int b)
{
    if(a>b)
    return a;
    else
    return b;
}
void dfs3(int w)
{
    int i,j,k,t1=0,t2=0;
    if(w>n)
    {
        for(i=1;i<=n;i++)
        if(r[i]>t1)
        t1=r[i];
        for(i=1;i<=n;i++)
        if(u[i]>t2)
        t2=u[i];
        if(t1>t2)
        {
            i=t1;
            t1=t2;
            t2=i;
        }
        if(t1*t2<ans)
        {
            ans=t1*t2;
            for(i=1;i<=top;i++)
            tt[wans[i]]=0;
            top=1;
            wans[1]=t1;
            tt[t1]=1;
        }
        else if(t1*t2==ans&&tt[t1]==0)
        {
            tt[t1]=1;
            top++;
            wans[top]=t1;
        }
        return;
    }
    for(i=0;i<w;i++)
    {
        l[w]=r[i];
        if(rev[w]==0)
        r[w]=l[w]+x[pl[w]];
        else
        r[w]=l[w]+y[pl[w]];
        t1=1000000;
        for(j=0;j<w;j++)
        if(u[j]<t1)
        {
            d[w]=u[j];
            if(rev[w]==0)
            u[w]=d[w]+y[pl[w]];
            else
            u[w]=d[w]+x[pl[w]];
            for(k=1;k<w;k++)
            if(max(d[k],d[w])<min(u[k],u[w])&&max(l[k],l[w])<min(r[k],r[w]))
            break;
            if(k>=w)
            t1=u[j];
        }
        d[w]=t1;
        if(rev[w]==0)
        u[w]=d[w]+y[pl[w]];
        else
        u[w]=d[w]+x[pl[w]];
        dfs3(w+1);
    }
}
void dfs2(int w)
{
    if(w>n)
    {
        dfs3(1);
        return;
    }
    rev[w]=1;
    dfs2(w+1);
    rev[w]=0;
    dfs2(w+1);
}
void dfs1(int w)
{
    int i;
    if(w>n)
    {
        dfs2(2);
        return;
    }
    for(i=1;i<=n;i++)
    if(bj[i]==0)
    {
        bj[i]=1;
        pl[w]=i;
        dfs1(w+1);
        bj[i]=0;
    }
}
main()
{
    for(i=1;i<=n;i++)
    scanf("%d%d",&x[i],&y[i]);
    dfs1(1);
    top=0;
    for(i=1;i<=n*50;i++)
    if(tt[i]>0)
    {
        top++;
        wans[top]=i;
    }
    printf("%d\n",ans);
    for(i=1;i<=top;i++)
    printf("%d %d\n",wans[i],ans/wans[i]);
}

后记

上面这个做法有拓展性，什么意思呢，就是不一定是 4 个矩形，也可以是 5 个甚至 6 个矩形（时间限制需要开到 3 秒），而更多矩形的情况也能在数组开到足够大、运行时间足够长的前提下得出答案，这只需要将代码开头的 const int n=4; 其中的 4 改掉就可以实现，而不需要分更多情况讨论。