题解 UVA103 Stacking Boxes

UVA103堆垛箱的解决方案。

【题意简述】

给你\(k\) \(n\)维的盒子，尽量一层一层最多装几个。

【题目分析】

这个问题的数据范围比较小，很多人第一眼可能会想到\(dfs\)或者\(dp\)。其实这个问题不需要指数算法。

第一步显然是先对嵌套关系进行预处理。这里有些人可能会用DFS一个一个的搜索，但还是用一个贪婪的思想比较好。我们先来看一个问题：

UVA11292

意思是：a体积和b体积分别有n个物品和m个箱子，每个箱子有重量x，所以需要将n个物品分别放入m个箱子中(每个箱子只能装一个物品)，这样可以将箱子的总重量降到最低。

这个问题是《算法竞赛入门经典——训练指南》的第一个例子。对于一个大容量的盒子，显然应该装一个大的物品，这样才不会浪费。所以可以按照箱子的体积从小到大排序，按照物品的体积从小到大排序，然后一一对应。

回过头来看，这个问题的盒子嵌套关系其实是上述问题的特例。然后我们可以对每个盒子的每个维度进行从小到大的排序，这样就可以对每个盒子之间的嵌套关系进行预处理。

处理好大小关系后怎么办。当一个主题需要输出路径时，显然有必要使用一个可以记录路径的方法。这里我用拓扑排序，因为它思维简单，效率高。

具体做法如下：

从小到大输入并排序每个框的每个维度。

枚举框来处理对之间的嵌套关系。从小盒子到大盒子连接一条有向边，使大盒子的穿透\ (\)。

排序和计算\(dp\)，并保存路径。

统计答案。

使用\(dfs\)查找路径和输出。

有关实现的详细信息，请参见代码：

#includebits/stdc。h

#定义整数长

#定义inf0x3f3f3f

使用命名空间标准；

int read(){ 0

int w=0，h=1；char ch=getchar()；

while(ch ' 0 ' | | ch ' 9 '){ if(ch=='-')h=-h；ch=getchar()；}

while(ch=' 0 ' ch=' 9 '){ w=w * 10 ch-' 0 '；ch=getchar()；}

返回w * h；

}

int k，n；

int box[35][15]；

结构节点{

int紧挨着；

} edge[200010]；

int head[35]，num

int in[35]，dp[35]，来自[35]；//dp[i]表示以I为最外层可以嵌套的最大盒子数，从[i]记录第I个盒子嵌套最多时I包含哪个盒子。

queueintq

void add(int u，int v){ 0

边[数]。next=head[u]；

边[数]。to=v；

head[u]=num；

}

void topo(){ 0

memset(dp，0，sizeof(DP))；

for(int I=1；I=k；(一)

if(！in[i])q.push(i)，dp[i]=1，从[I]=-1；

while(！q . empty()){ 0

int u=q . front()；q . pop()；

for(int I=head[u]；我；i=edge[i]。下一个){ 0

int v=edge[i]。去；

在[v]-；

//dp[v]=max(dp[v]，DP[u]1)；

if(dp[u] 1dp[v])

DP[v]=DP[u]1；

from[v]=u；

}

if(！in[v])q . push(v)；

}

}

}

无效DFS(int u){ 0

if(来自[u]==-1){ 0

printf('%lld '，u)；

返回；

}

dfs(来自[u])；

printf('%lld '，u)；//注意迭代后的输出，迭代后的输出和返回。

}

签名main(){ 0

while(scanf('%lld%lld '，k，n)！=EOF){ 0

//k=read()；n=read()；

memset(in，0，sizeof(in))；

memset(box，0，sizeof(box))；

memset(from，0，sizeof(from))；

memset(head，0，sizeof(head))；//需要初始化多个输入。

num=0；

for(int I=1；I=k；I){ 0

for(int j=1；j=n；j)

框[I][j]=read()；

排序(框[i] 1，框[I]n1)；//将每个框的每个维度从小到大排序。

}

for(int I=1；I=k；(一)

for(int j=1；j=k；j ){

bool标志=1；

for(int l=1；l=n；l)

if(box[i][l]=box[j][l])标志=0；

if(标志){ 0

添加(j，I)；//构建边缘。

在[i]中；

//printf('%lld可以放入%lld\n '，j，I)；

}

}

topo()；//拓扑排序

int ans=0，id；

for(int I=1；I=k；I){ 0

//ans=max(ans，DP[I])；

if(dp[i]ans){

ans=DP[I]；//统计答案

id=I；

}

}

printf('%lld\n '，ans)；

DFS(id)；puts(' ')；

}

返回0；

}