[USACO09OCT]津贴Allowance[贪心]

题面

首先面值大于$latex C$的硬币肯定只能直接计入答案. 剩下的硬币肯定要凑出尽可能接近$latex C$的面值, 策略是在面值不超过$latex C$的前提下优先使用大面值, 因为这样可以在使现在和将来避免浪费钱的前提下凑近$latex C$. 如果不能恰好凑出$latex C$而剩余$latex x$必须浪费钱时, 就可以优先用小面值补全$latex x$, 来使浪费最小化.

赞(0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址