【BZOJ】1229 [USACO2008 Nov]toy 玩具

【算法】三分+贪心

【题解】

数据范围小的版本:餐巾计划

这题不是使用最小费用流的下凸函数,因为这题是要满足最大流,那么这题到底在三分什么?

三分的这个函数,其实是总费用随卖出玩具量变化而变化的函数,此时的流量一直是满流的。可以想象一下,当卖出玩具的流量在总流量中占比小时,许多都得洗,花费巨大;继续卖出玩具直至到达一个平衡点时,总费用刚好最低;卖出过多时,冗余了很多,花费巨大。因此这是一个下凸函数。

为什么要三分玩具卖出量?因为可以根据玩具卖出量贪心求解,不用慢速的网络流。三分得到卖出玩具量,将这个玩具量先贪心使用,然后将用过的放进快洗队列,超过天数的从快洗队列对头拿进慢洗队列。玩具用完后贪心取慢洗队列,若慢洗空了就在快洗中取最近刚用的。

原文地址:https://www.cnblogs.com/onioncyc/p/6772738.html