把第 iii 个长方形放下时,只需在两种朝向里选一种:
限制是高度 ≤m\le m≤m。显然每个长方形彼此独立,总长度就是各自选择后的宽度之和,因此问题可分解为对每个 iii 局部做最优选择。
小美有 nnn 个长方形,第 iii 个长方形的两条边长分别为 xi,yix_i,y_ixi,yi ;
小美拥有一个仅包含第一象限的平面直角坐标系;
小美希望将这 nnn 个长方形按顺序(可以旋转)放置在 xxx 轴上,不允许重叠,并且每个长方形放置后的高度不超过 mmm ,保证 max(min(xi,yi))≦mmax(min(x_i,y_i))≦mmax(min(xi,yi))≦m ;
本题属于以下题库,请选择所需题库进行购买
ScanQRCodePrompt
请使用微信扫描下方二维码完成注册