POJ1020解题报告

很久没有更新啦,最近真的有点忙,都没有时间写博客
最近没有太做机器学习的内容,刷了一些OJ题,很多题目也让我回想起了高中NOIP时候的经历
昨天写了POJ1020,一道比较有意思的DFS题目,在这里做一点小的记录

题目

Anniversary Cake

Description

Nahid Khaleh decides to invite the kids of the “Shahr-e Ghashang” to her wedding anniversary. She wants to prepare a square-shaped chocolate cake with known size. She asks each invited person to determine the size of the piece of cake that he/she wants (which should also be square-shaped). She knows that Mr. Kavoosi would not bear any wasting of the cake. She wants to know whether she can make a square cake with that size that serves everybody exactly with the requested size, and without any waste.

Input

The first line of the input file contains a single integer t (1 ≤ t ≤ 10), the number of test cases, followed by input data for each test case. Each test case consist of a single line containing an integer s, the side of the cake, followed by an integer n (1 ≤ n ≤ 16), the number of cake pieces, followed by n integers (in the range 1..10) specifying the side of each piece.

Output

There should be one output line per test case containing one of the words KHOOOOB! or HUTUTU! depending on whether the cake can be cut into pieces of specified size without any waste or not.

Sample Input

2
4 8 1 1 1 1 1 3 1 1
5 6 3 3 2 1 1 1

Sample Output

KHOOOOB!
HUTUTU!

Source

Tehran 2002, First Iran Nationwide Internet Programming Contest

题目分析

简单解释一下题目
核心:使用小正方形装填大正方形,如果恰好可以填满,输出KHOOOOB!,如果不能填满,或者填不下输出
HUTUTU!
输入方式:
第一个数字表示测试数据的个数,之后的每一行表示一组测试数据
每组测试数据
第一个数字代表了大盒子的边长
第二个数字代表了小盒子的个数
之后n个数字代表了n个小盒子的边长

用样例输入打个比方:大盒子边长为4,小盒子有8个,有五个边长为1的小盒子,一个边长为3的小盒子
如图所示:

POJ1020

看到这个题第一个反应就是贪心,但是贪心对于几种特殊情况不能处理
比如这个数据:
1
10 14 1 1 1 1 1 4 4 3 3 3 3 3 3 3
结果是 KHOOOOB!
画出来的效果
POJ1020

此题 我们使用 DFS的方法。

算法描述

我们从上到下,从左到右逐个装填小正方形,如果盒子被填满则返回 true,如果盒子无法被填满则返回 false

1.创建两个数组
Col[41]表示行数,其中第 i 行的前Col[i]列已经被占用
Cake[11]表示小盒子的个数,Cake[i]表示边长为 i 的小盒子有 i 个

2.输入数据
将每一组的小盒子的数据存储在Cake中
同时记录下大盒子的尺寸(size) 与 小盒子个数(number)

3.DFS
建立一个变量 found 表示 是否可以放置。
参数 currNum 为当前的dfs的次数,如果dfs的次数与number相等,则return true
否则开始搜索
使用 j 从大到小遍历Cake
找到Col中数值最小的那一个 minRow ,(minRow,col[minRow])作为装填小正方形的起始位置(就是最靠左上的位置)
通过minRow+j-1<=size&&col[minRow]+j<=size判断当前位置是否可以放得下边长为 j 的正方形
如果可以
使用 i 遍历 Col 中 minRow 到 minRow+j 的数字,如果 col[i]> col[minRow],则表示 i 行有多余的盒子,无法放置,则break
循环完成后,如果 i == minRow + j ,表示可以以(minRow,col[minRow])为左上的位置可以放置边长为 j 的小盒子, found = true。

如果 found == true
Cake[j]减1,表示用掉了一个小盒子
使用 i 遍历 Col 中 minRow 到 minRow+j 的数字,col[i] = col[i]+j 表示该部分盒子被占用。
开始下一次,dfs(currNum+1),如果全部都成功则返回 true,否则返回 false

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <iostream>
#include <cstring>
using namespace std;
int Cake[11]={0};
int col[41]={0};//col代表每一行 col的内容代表每一行的钱多少列被占用
int getMinCol(int size)
{
int min =col[1];
int minRow=1;
for(int i=1;i<=size;i++)
{
if(col[i]<min) {
min = col[i];
minRow = i;
}
}
return minRow;
}
bool dfs(int currNumber,int Number,int size)
{
int i=0,j=0,minRow=0;
bool found;
if(currNumber == Number) return true;
minRow = getMinCol(size);
for(j = 10;j>0;j--)
{
found = false; //注意要设置为false 会出现负数 永远都可以成功
if(Cake[j]>0 && minRow+j-1<=size&&col[minRow]+j<=size)
{
for(i = minRow;i<minRow+j;i++)
{
if(col[i]> col[minRow]) break;
}
if(i == minRow + j ) found = true;
}
//如果该位置可以放下这个盒子
if(found)
{
//标记这个位置已经被使用过
Cake[j]--;
for(i = minRow;i<minRow+j;i++)
{
col[i] = col[i]+j;
}
if(dfs(currNumber+1,Number,size)) return true;
//回溯
for(i =minRow;i<minRow+j;i++) //最后错在这里
{
col[i] = col[i]-j;
}
Cake[j]++;
}
}
return false;
}
int main()
{
int num;
cin>>num;
while (num--)
{
int size,number;
cin>>size;
cin>>number;
int sum=0;
memset(Cake,0,sizeof(Cake));
memset(col,0,sizeof(col));
for(int i=0;i<number;i++)
{
int c;
cin>>c;
Cake[c]++;
sum+=c*c;
}
if(sum!=size*size) cout<<"HUTUTU!"<<endl;
else {
if (!dfs(0, number, size)) cout << "HUTUTU!" << endl;
else
cout << "KHOOOOB!" << endl;
}
}
}