P2439 [SDOI2005]阶梯教室设备利用 And P1868 饥饿的奶牛 题解
【题目链接】
P2439 P1868
【解题思路】
我们先来思考【P2493】,考虑用动态规划来做。
为了使动态规划没有后效性,我们需要先对演讲的时间按照一定的顺序来排序,这样我们就可以保证动态规划是单调递增的。
我们按照右端点从小到大排,到时后就可以找出一个第一个比左端点大的,就可以进行状态转移。
我们定义
d
i
d_i
di 为排序后前
i
i
i 个演讲的最长时间,则
【题目链接】
P2439 P1868
【解题思路】
我们先来思考【P2493】,考虑用动态规划来做。
为了使动态规划没有后效性,我们需要先对演讲的时间按照一定的顺序来排序,这样我们就可以保证动态规划是单调递增的。
我们按照右端点从小到大排,到时后就可以找出一个第一个比左端点大的,就可以进行状态转移。
我们定义
d
i
d_i
di 为排序后前
i
i
i 个演讲的最长时间,则
共有 0 条评论