当前位置：首页 > news >正文

UVa 366 Cutting Up

news 2026/5/25 11:56:14

题目描述

拼布者经常需要将布料切割成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叠加。

算法步骤

用vector<pair<int, 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//// 版权所有（C）2026，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;intmain(){intl,h,w;while(cin>>l>>h>>w){if(l==0&&h==0&&w==0)break;// 当前所有矩形的集合，每个矩形用 (width, height) 表示vector<pair<int,int>>pieces;pieces.push_back({w,h});intcuts=0;while(true){// 收集所有需要切割（面积 > 1）的矩形vector<pair<int,int>>needToCut;for(autop:pieces)if(p.first*p.second>1)needToCut.push_back(p);if(needToCut.empty())break;// 全部是 1x1，结束// 按面积降序排序，优先切大块sort(needToCut.begin(),needToCut.end(),[](pair<int,int>a,pair<int,int>b){returna.first*a.second>b.first*b.second;});vector<pair<int,int>>newPieces;inttake=min(l,(int)needToCut.size());// 本次最多切 l 个// 对选中的矩形，每个都从较长边的一半处切一刀for(inti=0;i<take;i++){autop=needToCut[i];if(p.first>=p.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(inti=take;i<(int)needToCut.size();i++)newPieces.push_back(needToCut[i]);pieces=newPieces;cuts++;}cout<<h<<" by "<<w<<" takes "<<cuts<<" cuts\n\n";}return0;}