[luoguP1280]尼克的任务

原题

神奇的一道没办法划分类别的dp题。

看上去就像背包,有时间有费用

但试了背包的做法发现不对啊,只能弄出最大费用或最小价值

卡在从后往前转移什么,应该怎么转移的阶段上,

没有意识到由于数据范围小,没有任务的空闲时间是可以直接加1解决的orz

从后往前转移空闲的时间,

以有任务的时间点作为转移阶段和决策点,

以任务结束时对应的空闲时间作为转移对象。

questions left

  1. 从后往前递推的必要性

原文
此时有任务(不在工作状态)就必须选,有很多个就选一个,所以当这个时间只有一个状态开始的时候,我们是没有任何的话说的,但是如果有很多的任务同时开始,我们要选取最优的那个取决这个任务结束后的情况,但是任务结束后的情况我们之前有没有推过,所以我们要倒着推

2.f[1]不是"空闲时间"(f[i]的最大值)最长的原因

在进行状态转移时只在任务开始点进行转移,任务进行中的时间仍被视作“空闲时间”+1,这样导致f[i]存储的值不一定与其定义相吻合,但由于任务进行过程中的f[i]不会被转移,所以对题目最终解没有影响

原文地址:https://www.cnblogs.com/StarOnTheWay/p/10629209.html