UVa 366 Cutting Up

题目描述拼布者经常需要将布料切割成1×11 \times 11×1的小正方形。他们有一种特殊工具旋转切割刀可以一次切割多层布料切割层数的上限由布料类型决定题目输入的第一个参数KKK。切割时无论切割长度是多少难度都是一样的因此问题的关键是最小化切割次数而不是切割长度。切割规则如下布料可以叠放且叠放的布料不需要形状完全相同。切割之间可以重新排列布料。布料不能被折叠。切割必须沿整数坐标进行即从边到边将一块布料切成两块。最终必须得到m×nm \times nm×n个1×11 \times 11×1的小正方形没有浪费。输入包含多行每行三个整数KKK最大可切割层数1≤K≤2001 \le K \le 2001≤K≤200、mmm高度1≤m≤201 \le m \le 201≤m≤20、nnn宽度1≤n≤201 \le n \le 201≤n≤20。输入以0 0 0结束。输出格式为m by n takes x cuts每组输出后跟一个空行。题目分析这是一道具有特殊性质的最优化问题。直觉上切割布料的过程可以看作一开始有一块m×nm \times nm×n的矩形每次操作可以选择若干块布料数量不超过KKK将它们叠放在一起然后沿某条直线切一刀使得每块被切中的布料都分成两块更小的矩形。最终目标是全部变成1×11 \times 11×1。由于m,n≤20m, n \le 20m,n≤20状态空间理论上有限但直接BFS\texttt{BFS}BFS或DP\texttt{DP}DP会遇到两个困难状态表示复杂多重集最多400400400种不同的矩形每种数量可达400400400。每次切割可以同时处理多种不同形状的矩形分支因子极大。然而题目允许不同形状叠放这一特性大大简化了问题我们不再需要为每种形状单独考虑切割而是可以一次性切割当前所有“还需要被切”的矩形中最需要切的那些。解题思路贪心策略的合理性核心贪心策略是每一轮从所有尚未变成1×11 \times 11×1的矩形中选择面积最大的min⁡(K,需要切的矩形总数)\min(K, \text{需要切的矩形总数})min(K,需要切的矩形总数)个矩形每个矩形都沿着较长边的一半向下取整切一刀其余矩形保留不动。重复直到全部是1×11 \times 11×1。为什么这样能得到最优解一刀切多块由于允许不同形状叠放一次切割可以同时作用于多个矩形因此我们希望在每一刀中尽可能多地切割“大块”的矩形因为大块矩形需要更多次切割才能变小。按面积排序面积越大的矩形距离1×11 \times 11×1的“距离”越远优先处理它们可以更快地减少总工作量。沿较长边中间切这是最平衡的切法可以最大化切完后两块的“最小面积”从而让两块都能在后续被继续切割避免出现细长条需要额外切割的情况。实际上对于矩形每次切成两半或尽可能接近一半是最优的切割策略。与BFS\texttt{BFS}BFS或DP\texttt{DP}DP的关系理论上本题可以用BFS\texttt{BFS}BFS精确求解但状态空间巨大每种矩形的数量范围000到400400400有400400400种矩形BFS\texttt{BFS}BFS会组合爆炸。而本题的数据范围m,n≤20m,n \le 20m,n≤20和允许不同形状叠放使得贪心策略恰好是全局最优的。这种贪心可以被视为一种基于优先级的贪心BFS\texttt{BFS}BFS每一步都选择当前最紧迫的任务进行切割。DP\texttt{DP}DP方法也不可行因为切割过程涉及并行处理多个矩形无法简单地用单矩形的DP\texttt{DP}DP叠加。算法步骤用vectorpairint, int存储当前所有矩形的尺寸(width, height)初始只有一块(n, m)。初始化切割次数cuts 0。循环直到所有矩形都是1×11 \times 11×1收集所有面积大于111的矩形到needToCut。按面积降序排序。取前take min(K, needToCut.size())个矩形。对这些矩形若宽度 ≥ 高度则水平切将宽度分成width/2和width - width/2否则垂直切。未选中的矩形直接保留。切割次数加111。输出结果。复杂度分析每轮切割需要处理的矩形个数最多为当前布料的总块数。初始为111块之后每切一刀会增加若干块。由于每次切掉最大的矩形且切法平衡矩形数量增长较慢。总切割次数不超过m×nm \times nm×n最坏情况每次只切一块实际远小于此。空间复杂度O(m×n)O(m \times n)O(m×n)。代码实现// Cutting Up// UVa ID: 366// Verdict: Accepted// Submission Date: 2026-05-16// UVa Run Time: 0.010s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(){intl,h,w;while(cinlhw){if(l0h0w0)break;// 当前所有矩形的集合每个矩形用 (width, height) 表示vectorpairint,intpieces;pieces.push_back({w,h});intcuts0;while(true){// 收集所有需要切割面积 1的矩形vectorpairint,intneedToCut;for(autop:pieces)if(p.first*p.second1)needToCut.push_back(p);if(needToCut.empty())break;// 全部是 1x1结束// 按面积降序排序优先切大块sort(needToCut.begin(),needToCut.end(),[](pairint,inta,pairint,intb){returna.first*a.secondb.first*b.second;});vectorpairint,intnewPieces;inttakemin(l,(int)needToCut.size());// 本次最多切 l 个// 对选中的矩形每个都从较长边的一半处切一刀for(inti0;itake;i){autopneedToCut[i];if(p.firstp.second){// 宽度 高度水平切newPieces.push_back({p.first/2,p.second});newPieces.push_back({p.first-(p.first/2),p.second});}else{// 高度 宽度垂直切newPieces.push_back({p.first,p.second/2});newPieces.push_back({p.first,p.second-(p.second/2)});}}// 未选中的矩形原样保留for(intitake;i(int)needToCut.size();i)newPieces.push_back(needToCut[i]);piecesnewPieces;cuts;}couth by w takes cuts cuts\n\n;}return0;}总结本题的关键在于认识到允许不同形状叠放使得我们可以在一刀中同时切割多个矩形从而将问题转化为一个贪心过程每次优先切割当前面积最大的若干个矩形且采用最平衡的切法。这种贪心策略在该问题的约束下能够达到全局最优代码实现简洁高效。