【题解】P1280 尼克的任务

题目链接(洛谷)

题目大意

尼克一天工作$n$分钟,从第$1$分钟开始到第$n$分钟结束。一共有已给出的$k$个任务需要完成。

如果在同一时刻有多个任务需要完成,尼克可以任选其中的一个来做,而其余的则由他的同事完成;反之如果只有一个任务,则该任务必需由尼克去完成;假如某些任务开始时刻尼克正在工作,则这些任务也由尼克的同事完成。

如果某任务于第$p$分钟开始,持续时间为$t$分钟,则该任务将在第$(p+t-1)$分钟结束。计算尼克最大的空闲时间是多少。

$n,k\le 1e4$

分析

设$dp_i$是$1-i$的空闲时间,发现这与后面选择有关,于是想到设$dp_i$为$i-n$的最大空闲时间

转移方程:

如果本时刻没有任务开始:$dpi=dp{i+1}+1$

如果本时刻有任务开始:$dpi=\max{dp{i+t}}$

代码

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
#include<bits/stdc++.h>
using namespace std;
int n,k;
struct node{
int p,t;
}q[10004];
int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') w=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
s=(s<<1)+(s<<3)+ch-'0';
ch=getchar();
}
return s*w;
}
bool cmp(node a,node b){
return a.p>b.p;
}
int sum[10004],dp[10004],num=1;
int main(){
n=read(),k=read();
for(int i=1;i<=k;i++){
q[i].p=read(),q[i].t=read();
sum[q[i].p]++;
}
sort(q+1,q+k+1,cmp);
for(int i=n;i>=1;i--){
if(sum[i]==0){
dp[i]=dp[i+1]+1;
continue;
}
for(int j=0;j<sum[i];j++){
if(dp[i]<dp[i+q[num].t]){
dp[i]=dp[i+q[num].t];
}
num++;
}
}
cout<<dp[1];
return 0;
}