1. 题目

传送门= ̄ω ̄=

2. 题解

考虑倒推。
设$f(i)$为时刻$i$到时刻$n$之间的最大空暇时间。
如果时刻$i$无任务开始,显然$f(i)=f(i+1)+1$。
否则枚举开始于时刻$i$的任务,设当前枚举的任务结束时间为$j$,则$f(i)=max(f(j+1))$。
至于保存每个时刻有哪些任务开始,用链表(或者模拟,即链式前向星)即可。

还有一点要注意的,一个任务开始与$a$,持续时间为$b$,那么它的结束时间不是$a+b$而是$a+b-1$。
下面的代码中我直接用$a+b$表示任务结束时间,这样在算$f(i)=max(f(j+1))$时就不用加一了。

代码:

#include <bits/stdc++.h>
using namespace std;
static const int ms=10005;
int n,k,t[ms],nxt[ms],head[ms],ls,f[ms];
void addt(int a,int b){t[ls]=b,nxt[ls]=head[a],head[a]=ls++;}
int main()
{
    scanf("%d%d",&n,&k),memset(head,-1,sizeof(head));
    for(int i=1,a,b;i<=k;i++)scanf("%d%d",&a,&b),addt(a,a+b);
    for(int i=n;i>=1;i--)
        if(head[i]==-1)f[i]=f[i+1]+1;
        else for(int j=head[i];j!=-1;j=nxt[j])f[i]=max(f[i],f[t[j]]);
    printf("%d\n",f[1]);
    return 0;
}
分类: 所有

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *