ZJU/ZOJ 1093 Monkey and Banana 解题报告

题目大意是给出n种箱子的3边长，每种箱子有若干个，你可以选择任意两条边作为底面，叠在上面的箱子的地面的长宽必须严格小于下面的箱子，问最多能够叠多高。

很明显一种箱子只能抓化为3个有用的箱子（长大于宽），另外3种组合（宽大与长）是没有意义的。对这些抓化完成的箱子以长为第一关键字，宽为第二关键字，进行升序排序。这样即可抓化为类似最长不降/不升序列的模型进行DP，状态转移方程是f[i]=max(f[i],f[j]+box[i].z)(1<=i<j<=n)。f[i]表示将第i个箱子叠在最上层时可以叠的最大高度，box[i].z表示第i个箱子的高度。

3067593    2008-09-12 19:18:52    Accepted    1093    FPC    00:00.00    408K    IwfWcf