rent专题

SPOJ RENT(简单动归)

暑期个人赛第四场 快被这道题搞死了。又是题意理解有误 题意:有n个订单,每个订单有开始时间,占用时间,愿意支付的money3个参数,要求在这n个订单中选择不冲突的的订单使得money总和最大。 思路:对订单的开始时间或者结束时间排序,然后用动归求最优解, 如果对开始时间从小到大排序,则动归顺序应从后向前,如果对结束时间从小到大排序,则动归顺序应该从前向后。 对于每个订单决策就是选择or丢