1158 尼克的任务

时间限制: 1 s

空间限制: 128000 KB

题目等级 : 黄金 Gold

题目描述 Description

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

尼 克的一个工作日为N分钟，从第一分钟开始到第N分钟结束。当尼克到达单位后他就开始干活。如果在同一时刻有多个任务需要完成，尼克可以任选其中的一个来 做，而其余的则由他的同事完成，反之如果只有一个任务，则该任务必需由尼克去写成，假如某些任务开始时刻尼克正在工作，则这些任务也由尼克的同事完成。如 果某任务于第P分钟开始，持续时间为T分钟，则该任务将在第P+T-1分钟结束。

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

输入描述 Input Description

输入数据第一行包含两个用空格隔开的整数N和K，1≤N≤10000，1≤K≤10000，N表示尼克的工作时间，单位为分，K表示任务总数。

接下来共有K行，每一行有两个用空格隔开的整数P和T，表示该任务从第P分钟开始，持续时间为T分钟，其中1≤P≤N，1≤P+T-1≤N。

输出描述 Output Description

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

样例输入 Sample Input

15 6

1 2

1 6

4 11

8 5

8 1

11 5

样例输出 Sample Output

4

/*

DP.

f[i]表示以i开始的最大空闲时间.

这种资源分配型DP就应该从后向前转移orz.

因为否则就会有后效性.

我们枚举一个开始时间.

然后枚举同等开始时间的结束时间取优.

这样不会影响前面的状态并且出现了状态记忆.

如果这个时间没任务.

f[i]=f[i+1]+1.

否则枚举做这个任务产生的后果状态取优.

*/

#include<iostream>

#include<cstdio>

#include<algorithm>

#define MAXN 10001

using namespace std;

struct data{int x,y;}s[MAXN];

int m,n,f[MAXN];

bool cmp(const data &x,const data &y)

{

    return x.x<y.x;

}

int main()

{

    scanf("%d%d",&m,&n);

    for(int i=1;i<=n;i++)  scanf("%d%d",&s[i].x,&s[i].y);

    sort(s+1,s+n+1,cmp);

    for(int i=m;i>=0;i--)

    {

        bool flag=false;int x=-1;

        for(int j=1;j<=n;j++)

        {

            if(s[j].x==i&&f[i+s[j].y]>=x)

            {

                x=f[i+s[j].y];flag=true;

            }

        }

        if(flag) f[i]=x;

        else f[i]=f[i+1]+1;

    }

    printf("%d",f[1]);

    return 0;

}

/*

spfa最长路.

建边我们规定无任务时边权为1.

为了使图连通

我们在不是任务开始点的时刻建边.

因为我们要求的是[0,m]区间的ans.

但是会发现边界不好处理,所以我们区间后移一位.

*/

#include<iostream>

#include<cstdio>

#include<queue>

#include<cstring>

#include<algorithm>

#define MAXN 10001

using namespace std;

struct data{int x,y,v;}s[MAXN];

struct edge{int v,next,x;}e[MAXN*4];

int m,n,f[MAXN],tot,cut,head[MAXN],dis[MAXN];

bool b[MAXN];

bool cmp(const data &x,const data &y)

{

    return x.x<y.x;

}

void add(int u,int v,int z)

{

    e[cut].v=v;

    e[cut].x=z;

    e[cut].next=head[u];

    head[u]=cut++;

}

int spfa()

{

    memset(dis,-1,sizeof(dis));

    queue<int>q;q.push(1);dis[1]=0;b[0]=true;

    while(!q.empty())

    {

        int u=q.front();q.pop();

        for(int i=head[u];i;i=e[i].next)

        {

            int v=e[i].v;b[u]=false;

            if(dis[v]<dis[u]+e[i].x)

            {

                dis[v]=dis[u]+e[i].x;

                if(!b[v])

                  b[v]=true,q.push(v);

            }

        }

    }

    return dis[m+1];

}

int main()

{

    scanf("%d%d",&m,&n);

    for(int i=1;i<=n;i++)  scanf("%d%d",&s[i].x,&s[i].y);

    sort(s+1,s+n+1,cmp);

    for(int i=1;i<=n;i++)

    {

        add(s[i].x,s[i].x+s[i].y,0);

    }

    for(int i=1;i<=m;i++)

      if(!head[i]) add(i,i+1,1);

    printf("%d",spfa());

    return 0;

}

/*

写了个toop不对吖.

望路过大神指教orz.

*/

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define MAXN 10001

using namespace std;

struct data{int x,y,v;}s[MAXN];

struct edge{int v,next,x;}e[MAXN*2];

int m,n,f[MAXN],tot,cut,head[MAXN],dis[MAXN];

bool cmp(const data &x,const data &y)

{

    return x.x<y.x;

}

void add(int u,int v,int z)

{

    e[++cut].v=v;

    e[cut].x=z;

    e[cut].next=head[u];

    head[u]=cut;

}

int dfs(int u)

{

    if(dis[u]) return dis[u];

    for(int i=head[u];i!=-1;i=e[i].next)

    {

        int v=e[i].v;

        dfs(v);

        dis[u]=max(dis[u],dis[v]+e[i].x);

    }

    return dis[u];

}

int main()

{

    memset(head,-1,sizeof(head));

    scanf("%d%d",&m,&n);

    for(int i=1;i<=n;i++)  scanf("%d%d",&s[i].x,&s[i].y);

    sort(s+1,s+n+1,cmp);

    s[++n].x=m+1,s[n].y=m+1;

    for(int i=0;i<=n;i++)

    {

        int x=1e9;bool flag=false;

    for(int j=i+1;j<=n;j++)

      {

        if(s[j].x>s[i].y)

        {

            if(flag)

              if(s[j].x-s[i].y>x) break;

            x=s[j].x-s[i].y;

            add(i,j,s[j].x-s[i].y-1);

            flag=true;

        }

        }

    }

    printf("%d",dfs(0));

    return 0;

}