蒟蒻在DP之路上求索着

题目:传送门

题目描述

​ 尼克每天上班之前都连接上英特网,接收他的上司发来的邮件,这些邮件包含了尼克主管的部门当天要完成的全部任务,每个任务由一个开始时刻与一个持续时间构成。

​ 尼克的一个工作日为$N$分钟,从第一分钟开始到第$N$分钟结束。当尼克到达单位后他就开始干活。如果在同一时刻有多个任务需要完成,尼克可以任选其中的一个来做,而其余的则由他的同事完成,反之如果只有一个任务,则该任务必需由尼克去完成,假如某些任务开始时刻尼克正在工作,则这些任务也由尼克的同事完成。如果某任务于第$P$分钟开始,持续时间为$T$分钟,则该任务将在第$P+T-1$分钟结束。

​ 写一个程序计算尼克应该如何选取任务,才能获得最大的空暇时间。

数据规模与约定

对于所有的数据,$1\le N\le 10000,1\le K\le 10000$,保证每个任务起止时间都在$N$以内.

题解

​ 这道题看起来像是线段覆盖类问题,但是发现可以对一些贪心策略举出反例来.所以你以为是贪心?其实是DP哒(雾).我们首先考虑怎么设计状态.我们发现总时间的范围并不大,所以我们尝试设$f[i]$表示时间$1…i$能获得的最大摸鱼时间.然后在每一个时间点分类讨论或者选取一个最优任务….我们发现一个问题.那就是题目中,尼克在闲着的时候如果有任务开始,他必须接一个,不能选择继续闲着.所以当前的选择可能会影响后面有哪些选择可以选,即后效性,不能这样推.

​ 但是题目并没有对任务结束时尼克的状态进行什么限制.如果我们倒着推,是不是就能实行类似于上述正着推的策略呢?于是我们尝试设$f[i]$表示$i…n$尼克能获得的最大摸鱼时间.那么尼克在这个时间点可能有两种状态:

  1. 现在闲着:$f[i]=f[i+1]+1$.即继承之前推出的时间然后闲着的时间+1.
  2. 现在刚接到一个任务:$f[i]=max(f[i],f[i+T(j)]),P[j]=i$.

​ 你可能会问,为什么在任务中不算一个状态?因为我们求的是$i…n$的最优解,不看前面的.由于$i$是起始点,所以目前讨论 的范围内不可能有任务开始在之前.所以只能是刚接到一个任务.注意到我们需要维护满足$P[j]=i$的所有任务.这怎么做呢?我们可以对每一个时间点维护一个$vector$,如果一个任务的起始时间是$i$,我们就把它的持续时间推进时间点$i$的$vector$中.然后扫描就可以了.

​ 代码:

int n, k, f[10005];
vector<int> eds[10005];

int main() {
    read(n), read(k);
    for (int i = 1, x, y; i <= k; ++i)
        read(x), read(y), eds[x].push_back(y);
    for (int i = n; i >= 1; --i) {
        if (eds[i].empty())
            f[i] = f[i + 1] + 1;
        else for (int j = 0; j < eds[i].size(); ++j)
            f[i] = max(f[i], f[i + eds[i][j]]);
    }
    cout << f[1] << endl;
    return 0;
}

(其实这道题正着推其实也有办法?[擦汗])

——Gensokyo