当前位置：首页 > news >正文

P1280 尼克的任务【洛谷算法习题】

news 2026/6/4 2:34:05

P1280 尼克的任务

网页链接

P1280 尼克的任务

题目描述

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

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

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

输入格式

输入数据第一行含两个用空格隔开的整数n nn和k kk。

接下来共有k kk行，每一行有两个用空格隔开的整数p pp和t tt，表示该任务从第p pp分钟开始，持续时间为t tt分钟。

输出格式

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

输入输出样例 #1

输入 #1

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

输出 #1

说明/提示

数据规模与约定

对于100 % 100\%100%的数据，保证1 ≤ n ≤ 10 4 , 1 ≤ k ≤ 10 4 , 1 ≤ p ≤ n , 1 ≤ p + t − 1 ≤ n 1 \leq n \leq 10^4,1 \leq k \leq 10^4,1 \leq p \leq n,1 \leq p+t-1 \leq n1≤n≤104,1≤k≤104,1≤p≤n,1≤p+t−1≤n。

解题思路

本题核心是逆序动态规划，反向推导最优空闲时间，规避正向决策的后效性。定义dp[i]表示从第i ii分钟到下班的最大空闲时间。从最后一分钟向前遍历：若当前分钟无任务，空闲时间等于下一分钟空闲时间加1；若有任务，遍历所有任务，选择任务结束后空闲时间最大的方案。逆序遍历保证决策无后效，直接筛选最优任务，时间复杂度O ( n + k ) O(n+k)O(n+k)，完美适配n 、 k ≤ 10 4 n、k≤10^4n、k≤104的数据规模，高效算出最大空闲时间。

总结

核心逻辑：逆序DP从后往前计算各时间点最大空闲，无任务累加空闲、有任务选最优结束点。
关键操作：按任务开始时间分组、逆序遍历、状态转移取最大值。
效率保障：线性遍历无冗余计算，轻松处理万级数据，精准输出结果。

代码内容

#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll n,k,s,t;scanf("%lld%lld",&n,&k);vector<ll>v[10001];while(k--){scanf("%lld%lld",&s,&t);v[s].push_back(t);}ll f[10002]={0};for(ll i=n;i;i--){if(v[i].size()>0)for(ll j=0;j<(ll)v[i].size();j++)f[i]=max(f[i],f[i+v[i][j]]);elsef[i]=f[i+1]+1;}printf("%lld",f[1]);return0;}