把第 i 块纸板放下时,只需在两种朝向里选一种:
限制是高度 ≤H。显然每块纸板彼此独立,总长度就是各自选择后的宽度之和,因此问题可分解为对每个 i 局部做最优选择。
小蓝有 n 块矩形纸板,他打算将这些纸板按顺序沿墙壁竖直放置在地面上。纸板可以随意旋转,但放置后纸板在竖直方向上的尺寸不能超过墙壁上方的安全线高度 H。每块纸板有两个方向上的尺寸,放置时可以任选一个作为竖直尺寸、另一个作为水平方向的占据长度。已知对于每一块纸板,它较小的尺寸一定不超过 H。请问在满足要求的前提下,所有纸板占据墙壁的总长度最小是多少?
数据范围:纸板数量 n 满足 1≤n≤2imes105,安全线高度 H 满足 1≤H≤109。每块纸板的两个尺寸均为正整数且不超过 109。题目保证每块纸板较小的尺寸不超过 H。
第一行包含两个整数 n 和 H,分别表示纸板的数量和安全线的高度。 接下来 n 行,每行包含两个整数 ai,bi,表示第 i 块纸板的两个尺寸。
Scan the QR code below with WeChat to sign in
First-time scan will create your account automatically
请使用微信扫描下方二维码完成注册