题解 p1049【装箱问题】

0.前言

最开始用贪心水了一发，拿了80分，下个数据特判后就AC了（手动狗头）

1.正文

题目解析

题目中“使剩余空间最小”转化一下，其实就是求总体积最大值，不难看出是01背包。

注意点

最后答案记得相减求最小值。

代码实现

1. 贪心（参见前言），直接排序累加（题目的数据点也太水 了，竟然让我水到了80分/4个数据点）。

2. dp，套个01背包模板（一维数组优化版），稍微改动一下即可，实现原理可参考我的这篇博客中的代码实现。

Code

#include<cstdio>
#include