洛谷P1280《尼克的任务》

十一月 01, 2018 4077

线性DP

题目🔗

题目描述

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

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

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

Input / Output 格式 & 样例

输入格式

输入数据第一行含两个用空格隔开的整数 N 和 K(1≤N≤10000，1≤K≤10000) ， N 表示尼克的工作时间，单位为分钟， K 表示任务总数。

接下来共有 K 行，每一行有两个用空格隔开的整数 P 和 T ，表示该任务从第 P 分钟开始，持续时间为 T 分钟，其中 1≤P≤N ， 1≤P+T-1≤N 。

输出格式

输出文件仅一行，包含一个整数，表示尼克可能获得的最大空暇时间。

输入样例

1
2
3
4
5
6
7
15 6
1 2
1 6
4 11
8 5
8 1
11 5

输出样例

1
4

解题思路

DP

我们设f[i]表示在前i分钟内的最大空闲时间
但是发现第i分钟的空闲时间是由后面的任务决定的
所以我们考虑倒着扫一遍

我们设f[i]表示在第i \rightarrow n分钟内的最大空闲时间
转移方程：

  • 当第i分钟没有任务时，f[i] = f[i + 1] + 1
  • 当第i分钟有任务时，f[i] = std::max(f[i], f[i + seq[j]].time)，其中seq[j].time表示第j个任务的耗时

如何判断当前有没有任务？
我们开一个数组sum[i]表示第i分钟的任务个数
更新就很好更新了——
++sum[seq[j].startTime]，其中seq[j].startTime表示第j个任务的开始时间

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
/* -- Basic Headers -- */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>

/* -- STL Iterators -- */
#include <vector>
#include <string>
#include <stack>
#include <queue>

/* -- External Headers -- */

/* -- Defined Functions -- */
#define For(a,x,y) for (int a = x; a <= y; ++a)
#define Forw(a,x,y) for (int a = x; a < y; ++a)
#define Bak(a,y,x) for (int a = y; a >= x; --a)

/* -- Defined Words -- */

using namespace std;

namespace FastIO {
    
    inline int getint() {
        int s = 0, x = 1;
        char ch = getchar();
        while (!isdigit(ch)) {
            if (ch == '-') x = -1;
            ch = getchar();
        }
        while (isdigit(ch)) {
            s = s * 10 + ch - '0';
            ch = getchar();
        }
        return s * x;
    }
    inline void __basic_putint(int x) {
        if (x < 0) {
            x = -x;
            putchar('-');
        }
        if (x >= 10) __basic_putint(x / 10);
        putchar(x % 10 + '0');
    }
    
    inline void putint(int x, char external) {
        __basic_putint(x);
        putchar(external);
    }
}


namespace Solution {
    /*/
     *
     * 设f[i]表示i-n的空闲时间
     * f[i] = f[i+1] + 1（无任务）
     * f[i] = max(f[i], f[i + seq[x]])（有任务）
     *
    /*/
    const int MAXK = 10000 + 10;
    const int MAXN = MAXK;
    
    struct QwQ {
        int start, time;
    } qwq[MAXK];
    
    int n, k;
    int sum[MAXN];
    int f[MAXN];
    int num = 1;
    
    bool stlCmp(QwQ x, QwQ y) { return x.start > y.start; }
    
    void Work() {
        using FastIO::getint;
        n = getint();
        k = getint();
        For (i, 1, k) {
            qwq[i].start = getint();
            qwq[i].time = getint();
            ++sum[qwq[i].start];
        }
        sort(qwq + 1, qwq + 1 + k, stlCmp);
        // 既然是倒序，所以输入也要排序
        for (int i = n; i >= 1; --i) {
            if (sum[i] == 0) f[i] = f[i + 1] + 1; // 当前时刻没有任务
            else {
                for (int j = 1; j <= sum[i]; ++j) {
                    f[i] = std::max(f[i], f[i + qwq[num].time]); 
                    // 当前时刻有至少一个任务，把它们都扫一遍
                    ++num;
                    // 用一个变量 num 表示当前扫到的任务
                }
            }
        }
        FastIO::putint(f[1], '\n');
        // 输出
    }
}

int main(int argc, char *const argv[]) {
#define HANDWER_FILE
#ifndef HANDWER_FILE
    freopen("testdata.in", "r", stdin);
    freopen("testdata.out", "w", stdout);
#endif
    using namespace Solution;
    using namespace FastIO;
    Work();
    return 0;
}