LuoguP1280 尼克的任务 : 线性 dp
题目描述
尼克每天上班之前都连接上英特网, 接收他的上司发来的邮件, 这些邮件包含了尼克主管的部门当天要完成的全部任务, 每个任务由一个开始时刻与一个持续时间构成.
尼克的一个工作日为 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.
输出格式:
输出文件仅一行, 包含一个整数, 表示尼克可能获得的最大空暇时间.
- INPUT & OUTPUT's examples
- Input's e.g. #1
- 15 6
- 1 2
- 1 6
- 4 11
- 8 5
- 8 1
- 11 5
- Output's e.g. #
- 4
分析
比较简单的一道线性 dp 题目.
我们采用逆推的方式, 设 dp[i] 表示从后往前推到 i 的最大空闲时间.
首先, 如果第 i 个时刻没有工作, 那么就直接 dp[i] = dp[i+1] + 1 即可 (直接算上)
然后, 如果有工作, 那么我们就要选一个在任务结束后空闲时间最大的任务, 那么显然可以得出:
dp[i] = std::max(dp[i+Time[i][j])
这里我们用一个动态数组 std::vector<int> v[MAXN] 来储存时刻 i 开始的任务持续时间.
代码
- /* Headers */
- #include<cstdio>
- #include<cstring>
- #include<cmath>
- #include<cctype>
- #include<algorithm>
- #include<vector>
- #include<queue>
- #include<stack>
- #include<climits>
- #include<iostream>
- #include<map>
- #define FOR(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
- #define ROF(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
- #define FORL(i,a,b,c) for(long long i=(a);i<=(b);i+=(c))
- #define ROFL(i,a,b,c) for(long long i=(a);i>=(b);i-=(c))
- #define FORR(i,a,b,c) for(register int i=(a);i<=(b);i+=(c))
- #define ROFR(i,a,b,c) for(register int i=(a);i>=(b);i-=(c))
- #define lowbit(x) x&(-x)
- #define LeftChild(x) x<<1
- #define RightChild(x) (x<<1)+1
- #define RevEdge(x) x^1
- #define FILE_IN(x) freopen(x,"r",stdin);
- #define FILE_OUT(x) freopen(x,"w",stdout);
- #define CLOSE_IN() fclose(stdin);
- #define CLOSE_OUT() fclose(stdout);
- #define iOS(x) std::iOS::sync_with_stdio(x)
- #define Dividing() printf("-----------------------------------\n");
- namespace FastIO{
- const int BUFSIZE = 1 <<20;
- char ibuf[BUFSIZE],*is = ibuf,*its = ibuf;
- char obuf[BUFSIZE],*os = obuf,*ot = obuf + BUFSIZE;
- inline char getch(){
- if(is == its)
- its = (is = ibuf)+fread(ibuf,1,BUFSIZE,stdin);
- return (is == its)?EOF:*is++;
- }
- inline int getint(){
- int res = 0,neg = 0,ch = getch();
- while(!(isdigit(ch) || ch == '-') && ch != EOF)
- ch = getch();
- if(ch == '-'){
- neg = 1;ch = getch();
- }
- while(isdigit(ch)){
- res = (res << 3) + (res << 1)+ (ch - '0');
- ch = getch();
- }
- return neg?-res:res;
- }
- inline void flush(){
- fwrite(obuf,1,os-obuf,stdout);
- os = obuf;
- }
- inline void putch(char ch){
- *os++ = ch;
- if(os == ot) flush();
- }
- inline void putint(int res){
- static char q[10];
- if(res==0) putch('0');
- else if(res < 0){putch('-');res = -res;}
- int top = 0;
- while(res){
- q[top++] = res % 10 + '0';
- res /= 10;
- }
- while(top--) putch(q[top]);
- }
- inline void space(bool x){
- if(!x) putch('\n');
- else putch(' ');
- }
- }
- inline void read(int &x){
- int rt = FastIO::getint();
- x = rt;
- }
- inline void print(int x,bool enter){
- FastIO::putint(x);
- FastIO::flush();
- FastIO::space(enter);
- }
- /* definitions */
- const int MAXN = 1e4 + 10;
- int n,k;
- int dp[MAXN];
- std::vector<int> Time[MAXN];
- /* functions */
- int main(int argc,char *argv[]){
- scanf("%d%d",&n,&k);
- FOR(i,1,k,1){
- int p,t;
- scanf("%d%d",&p,&t);
- Time[p].push_back(t);
- }
- ROF(i,n,1,1){
- if(Time[i].size()> 0)
- FOR(j,0,Time[i].size()-1,1)
- dp[i] = std::max(dp[i],dp[i+Time[i][j]]);
- else dp[i] = dp[i + 1] + 1;
- }
- printf("%d\n",dp[1]);
- return 0;
- }
- Luogu1280
来源: http://www.bubuko.com/infodetail-3039155.html