P1280 尼克的任务

提交 19.94k
通过 10.36k
时间限制 1.00s
内存限制 125.00MB
题目提供者 洛谷
历史分数 无

提交记录

查看题解

标签

 
查看算法标签
进入讨论版

相关讨论

 
查看讨论

推荐题目

 
查看推荐
 

展开

题目描述

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

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

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

输入格式

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

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

输出格式

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

输入输出样例

输入 #1 
15 6
1 2
1 6
4 11
8 5
8 1
11 5
输出 #1 
4

思路

　　　依据题意，前面的选择会影响后面的选择，显然是一道线性动态规划问题。

　　 故设 f[i] 代表进行到 i 时刻，i∈（1，n），尼克所能休息的最大时间。

　　 之后来分析转移的过程：

　　 1、如何转移？

　　 显然，如果第 i 时刻没事做，休息的时间一定+1，此时 f[i] = f[i-1] + 1;

　　 如果有事做，则 f[i] = max( f[i], f[ i + 事件时长 ] );

　　 2、如何确保转移的正确性？

　　 我们可以考虑从 n -> 1 来转移，为什么呢？

　　 我们知道，如果 i + 1 时无事可做，则 f[i + 1] 一定 f[i] + 1，反之，如果 i - 1 时无事可做，i 时有事做，则不能确定此时的转移方法。

　　 时间复杂度也是小于等于 n方的

 

CODE

 1 #include <bits/stdc++.h>
 2 #define dbg(x) cout << #x << "=" << x << endl
 3 
 4 using namespace std;
 5 typedef long long LL;
 6 
 7 template<class T>inline void read(T &res)
 8 {
 9     char c;T flag=1;
10     while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
11     while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
12 }
13 
14 namespace _buff {
15     const size_t BUFF = 1 << 19;
16     char ibuf[BUFF], *ib = ibuf, *ie = ibuf;
17     char getc() {
18         if (ib == ie) {
19             ib = ibuf;
20             ie = ibuf + fread(ibuf, 1, BUFF, stdin);
21         }
22         return ib == ie ? -1 : *ib++;
23     }
24 }
25 
26 int qread() {
27     using namespace _buff;
28     int ret = 0;
29     bool pos = true;
30     char c = getc();
31     for (; (c < '0' || c > '9') && c != '-'; c = getc()) {
32         assert(~c);
33     }
34     if (c == '-') {
35         pos = false;
36         c = getc();
37     }
38     for (; c >= '0' && c <= '9'; c = getc()) {
39         ret = (ret << 3) + (ret << 1) + (c ^ 48);
40     }
41     return pos ? ret : -ret;
42 }
43 
44 const int maxn = 1e4 + 7;
45 int n,k,p,t;
46 int f[maxn];
47 
48 vector <int> v[maxn];
49 
50 int main()
51 {
52     read(n);
53     read(k);
54     for(int i = 1; i <= k; ++i) {
55         int p,t;
56         read(p);
57         read(t);
58         v[p].push_back(t);
59     }
60     for(int i = n; i > 0; --i) {
61         if(!v[i].size()) {
62             f[i] = f[i+1]+1;
63         }
64         else {
65             int d = v[i].size();
66             for(int j = 0; j < d; ++j) {
67                 f[i] = max(f[i], f[i + v[i][j]]);
68             }
69         }
70     }
71     cout << f[1] << endl;
72     return 0;
73 }
View Code