[洛谷1233] 木棍加工

Link: 1233 木棍加工 - 洛谷

大致题意是有很多长为ai宽为bi的木板,只有当一个木板的长和宽都小于等于前一个模板时才不需要准备时间。你可以调整模板的顺序,求最小的准备时间。

我们可以先根据长度排序(从小到大排,长度相等时按宽度从小到大排),那么排在后面的一定会在前面的某个之后做或者单独做第一个,这样的话你需要考虑的就只有宽度了。对于剩下的宽度,可以向“导弹拦截”那题一样贪心,也可以求宽度的最长下降子序列。

代码链接: R7496644 评测详情 - 洛谷

添加新评论

0%