12099专题

UVA 12099 The Bookcase(dp)

题意: 有N本书,第i本书有一个高度Hi和宽度Wi,现要求构建一个三层的书架,你必须把所有书放在书架上。设三层高度(该层最高的书的高度)之和为h,书架总宽度(即每层总宽度的最大值)为w,要求h×w尽可能小。 思路(抄自紫书): 首先我们可以考虑将所有书按高度从大到小排序。不妨设最高的书在第1层,且第二层的高度大于等于第三层的高度。 则我们可以定义状态d(i,j,k)为当前已经安排了i本书,第二