POJ 1020 - Anniversary Cake


问题描述

有一块边长为BoxSize的正方形的大蛋糕,现在给出n块不同尺寸的正方形的小蛋糕的边长,问是否能把大蛋糕按恰好切割为这n块小蛋糕,要求每块小蛋糕必须为整块。

解题思路

有技巧的DFS

可以把大蛋糕想象为一个蛋糕盒子,然后往里面装小蛋糕。

装蛋糕时遵循以下原则:

  • 自下而上,自左至右:即先装好盒子底部,再继续往上层装,且装每一层时都靠左边放蛋糕;
  • 大蛋糕优先装,因为小蛋糕灵活度比较高。

只要把问题变换为上述问题,我想对深搜比较熟悉的同学也会马上得到思路了,这个只是很简单的DFS思路。


但是本题的难点不在于怎样去DFS,而是每放入一个蛋糕后,怎样去标记盒子已经放有蛋糕的位置

我初始的做这题时,因为看到数据规模不大(Max_n=16Max_size=10,那么大蛋糕最大也就 40*40 ),于是我把尺寸为BoxSize的盒子划分为 BoxSize*BoxSize1*1 的格子,每放入一个大小为size的蛋糕,就用一个二重循环去标记 size*size 的格子。

最后是毫无悬念地TLE了。

看了别人的方法,发现或分格子的思路是正确的,但应该“按列标记”。不但把盒子看做多个 1*1 个格子,也把小蛋糕看做多个 1*1 的单位,建立一个一维数组 col[ BoxSize ] ,每放入一个蛋糕,则去记录每列的格子被填充的数目。

例如在第 2~4 列放入了一个 size=3 的小蛋糕,那么 col[2]+=3, col[3]+=3, col[4]+=3

有同学会问,为什么行不用计数?要是放入蛋糕后,该蛋糕底部出现部分悬空怎么处理?这个情况是不会出现的,因为当前DFS遵循先把底部放满原则,要是出现悬空,则会回溯。

更具体的处理方法请看程序注释。

测试数据

AC 源码

//Memory Time 
//208K  32MS 

#include<iostream>
using namespace std;

int BoxSize;      //盒子尺寸
int n;            //蛋糕的总个数
int SizeNum[11];  //各种尺寸的蛋糕个数
int col[41];      //把盒子纵行分割成BoxSize*BoxSize个1*1大小的小格子
                  //col[i]记录第i列被填充了的格子数

bool DFS(int FillNum)   //FillNum:已放入盒子的蛋糕数
{
    if(FillNum==n)
        return true;

    /*寻找格子数被填充最少的列,靠左优先*/
    int min=50;
    int prow;
    for(int i=1;i<=BoxSize;i++)
        if(min>col[i])
        {
            min=col[i];
            prow=i;
        }

    /*枚举各种尺寸的蛋糕自下而上地放入盒子*/
    for(int size=10;size>=1;size--)
    {
        if(!SizeNum[size])
            continue;

        //检查尺寸为size的蛋糕放入盒子时在纵向和横向是否越界
        if(BoxSize-col[prow]>=size && BoxSize-prow+1>=size)
        {
            //检查盒子从第prow列到第prow+size-1列,共size列的宽度wide中
            //是否每列剩余的空间都足够放入高度为size的蛋糕
            int wide=0;
            for(int r=prow;r<=prow+size-1;r++)
            {
                if(col[r]<=col[prow])  //比较各列的"填充数"
                {    //注意,这里若比较"未填充数"BoxSize-col[r]<size会TLE
                    wide++;       //虽然两个条件等价,但确实计算了3秒左右,不知何故
                    continue;
                }
                break;
            }

            if(wide>=size)
            {
                int r;
                //放入尺寸为size的蛋糕
                SizeNum[size]--;
                for(r=prow;r<=prow+size-1;r++)
                    col[r]+=size;

                if(DFS(FillNum+1))
                    return true;

                //回溯
                SizeNum[size]++;
                for(r=prow;r<=prow+size-1;r++)
                    col[r]-=size;
            }
        }
    }
    return false;
}

int main(void)
{
    int test;
    cin>>test;
    for(int t=1;t<=test;t++)
    {
        memset(SizeNum,0,sizeof(SizeNum));
        memset(col,0,sizeof(col));

        cin>>BoxSize>>n;

        int cnt=0;   //记录size>(BoxSize/2)的蛋糕个数
        int area=0;  //计算所有蛋糕的面积之和
        for(int i=1;i<=n;i++)
        {
            int size;
            cin>>size;
            area+=size*size;
            SizeNum[size]++;

            if(size>BoxSize/2)
                cnt++;
        }

        if(cnt>1 || area!=BoxSize*BoxSize)
        {
            cout<<"HUTUTU!"<<endl;
            continue;
        }

        if(DFS(0))
            cout<<"KHOOOOB!"<<endl;
        else
            cout<<"HUTUTU!"<<endl;
    }
    return 0;
}

相关资料


文章作者: EXP
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 EXP !
 上一篇
POJ 1009 - Edge Detection POJ 1009 - Edge Detection
POJ 1009 - Edge Detection Time: 1000MS Memory: 10000K 难度: 中级 分类: 模拟法 问题描述某种卫星使用一种叫做“run length encoding”的方式来储存大尺寸图片, 有
2011-09-21
下一篇 
POJ 2602 - Superlong sums POJ 2602 - Superlong sums
POJ 2602 - Superlong sums Time: 1000MS Memory: 65536K 难度: 初级 分类: 高精度算法 问题描述无。 解题思路非常恶心的大数相加 首先输入就够恶心了…哪有人逐位还要间断输入两个数的…
2011-09-16
  目录