hur专题

P3545 [POI2012] HUR-Warehouse Store

Portal. 反悔贪心。 想满足尽量多的天数,就要让时间尽可能的长。考虑顺次在每一天满足要求,如果有一天不能满足要求了,就查找前面满足的天里有没有要求比它高的,若有可以放弃那一天的选择而选择当前天,这样可以使时间尽可能地延长。 考虑为什么这样是正确的。首先,放弃之前天选择当前天这一决策一定不会更劣。同时还可以不断增加存货量,增大了后面满足要求的可能性。因此该决策是优的。 #include