题目链接（洛谷）
题目大意
尼克一天工作\(n\)分钟，从第\(1\)分钟开始到第\(n\)分钟结束。一共有已给出的\(k\)个任务需要完成。
如果在同一时刻有多个任务需要完成，尼克可以任选其中的一个来做，而其余的则由他的同事完成；反之如果只有一个任务，则该任务必需由尼克去完成；假如某些任务开始时刻尼克正在工作，则这些任务也由尼克的同事完成。
如果某任务于第\(p\)分钟开始，持续时间为\(t\)分钟，则该任务将在第\((p+t-1)\)分钟结束。计算尼克最大的空闲时间是多少。
\(n,k\le 1e4\)
分析
设\(dp_i\)是\(1-i\)的空闲时间，发现这与后面选择有关，于是想到设\(dp_i\)为\(i-n\)的最大空闲时间
转移方程：
如果本时刻没有任务开始：\(dp_i=dp_{i+1}+1\)
如果本时刻有任务开始：\(dp_i=\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;
}
|