Luogu1280 尼克的任务

Link

题意

​ 有一段长度为 n 的时间,有 k 个任务需要完成,每个任务从p开始一直持续t分钟,则在p+t-1的时刻结束.在某一时刻如果只有一个任务,那么这个任务必须要做.否则,若某个时刻有多个任务,可以任选其中一个做.问一种选择方案使空闲时间(不做任务的时间)最长.

题解

​ 首先可以考虑从前往后选任务,设 f[i] 表示[1,i]时刻可以获得的最大空闲时间.那么转移为:

​ f[i] += f[i+p_j + t_j]

​ 就是说,这一刻能获得的空闲时间肯定会跟选择的任务结束的时间的最大空闲时间挂钩.无法保证DP的无后效性,所以不妨考虑从后转移.

​ 设f[i]表示从 [i,n] 时刻可以获得的最大的空闲时间,那么状态有两种:

​ 1.这个时候已经选了任务并且还没结束

​ 2.这个时候没有在做任何任务且这个时候有任务可做

那么转移就比较显而易见了,开一个桶basket[]表示一条时间轴,在读入时处理某个时候有几个任务

当baket[i]=0,表示此时没有任务可做, f[i] = f[i+1]+1

否则, f[i] = min(f[i+a[k].t] |k \in {1,baket[i]})

尔后还需处理一个细节,就是入度的任务要按照起始时间排序.

Code

见代码

#include <bits/stdc++.h>
using namespace std;

const int SIZE = 10000 + 5;

int n, k;
int f[SIZE], basket[SIZE];

struct node {
    int st, t;
} a[SIZE];

inline int read()
{
    char ch = getchar();
    int f = 1, x = 0;
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); }
    return x * f;
}

inline int CMP(node a, node b) 
{
    return a.st > b.st;
}

int main()
{
    int cnt = 1;
    n = read(), k = read();
    for (int i = 1; i <= k; i++)    
        a[i].st = read(), a[i].t = read(), basket[a[i].st]++;
    std::sort(a + 1, a + k + 1, CMP);
    for (int i = n; i >= 1; i--) {
        if (!basket[i]) f[i] = f[i + 1] + 1;
        else {
            for (int j = 1; j <= basket[i]; j++) {
                if (f[i + a[cnt].t] > f[i]) 
                    f[i] = f[i + a[cnt].t];
                cnt++;
            }
        }
    }
    printf("%d", f[1]);
    return 0;
}

​