[POJ1017]Packets[贪心]

题面

题意: 要用尽量少的6*6的箱子放入一些1*1~6*6的物品, 设他们分别有$latex a_i$个.

首先答案至少要$latex a_6+a_5+a_4$这么多, 因为他们是不能多个并存的. 然后对于5*5和4*4的物品我们就可以贪心地在空隙中插入物品. 对于放了5*5的箱子每个可以插11个1*1. 对于放了4*4的箱子每个可以放5个3*3和7个1*1, 如果放不满就尽可能放1*1. 最后考虑3*3的, 尽量每4个放满一个箱子, 然后讨论剩余1, 2, 3个4*4时能插入多少个1*1和2*2. 最后剩下的1*1和2*2随便放.

由于放每个物品时都尽可能利用所有的空间, 并且都排除了不可行解(不可能放多个的情况), 可以出全局最优. 思路简单, 细节多, 情况要考虑周全.

赞(0)

评论 抢沙发

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