P2900 [USACO08MAR] Land Acquisition G

Farmer John 准备扩大他的农场，眼前他正在考虑购买 $N$ 块长方形的土地。 如果 FJ 单买一块土地，价格就是土地的面积。但他可以选择并购一组土地，并购的价格为这些土地中最大的长乘以最大的宽。比如 FJ 并购一块 $3 \times 5$ 和一块 $5 \times 3$ 的土地，他只需要支付 $5 \times 5=25$ 元， 比单买合算。 FJ 希望买下所有的土地。他发现，将这些土地分成不同的小组来并购可以节省经费。 给定每份土地的尺寸，请你帮助他计算购买所有土地所需的最小费用。

无

无

将所有土地分为三组： - 第一块土地为第一组，花费 $100 \times 1=100$； - 第二，三块土地为第二组，花费 $20 \times 15=300$； - 第四块土地为第三组，花费 $1 \times 100=100$； 总花费为 $500$，可以证明不存在更优的方案。