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；
}
内容来源网络，如有侵权，联系删除，本文地址：https://www.230890.com/zhan/67473.html