[每日算法]尼克的任务

题目描述

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

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

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

输入格式

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

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

输出格式

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

输入输出样例

样例#1	输出#1
15 6 1 2 1 6 4 11 8 5 8 1 11 5	4

说明/提示

• 对于 100% 的数据，保证 1≤n≤10^4,1≤k≤10^4,1≤p≤n,1≤p+t-1≤n。

题解

这个题是一个线性的动态规划问题，第i时刻的最大空闲时间是和后面i+选择任务的持续时间的时刻有关系的，如果正着找是不那么容易的，但是如果倒着查找就会容易很多，可以得到相应的状态转移方程：

如果本时刻无任务时，那么这个时刻的空闲时间为上一个时刻的最大空闲时间+1：f[i]=f[i+1]+1；

如果本时刻有任务，begins表示这个时刻的任务的持续时间，那么状态转移方程为：fx[i] = max(fx[i], fx【i + begins【i】【j】】)。

源代码

#include <iostream>
#include <vector>
using namespace std;

vector<int> begins[10002];        //begin存在时刻i开始的任务结束的时间
int fx[10002];                   //存储每个时间点的最大空闲值
int main()
{
    int i, j;
    int n, k;                    //n为工作日的持续时间,k为任务数
    cin >> n >> k;
    int be, co;
    for (i = 0;i < k;i++)
    {
        cin >> be >> co;
        begins[be].push_back(co);
    }

    for (i = n; i >= 1; i--) 
    {//倒序处理每个时刻
        if (!begins[i].empty())
        {//说明有任务需要做
            for (j = 0; j < begins[i].size(); j++)
            {//获取时间最长的那一个
                fx[i] = max(fx[i], fx[i + begins[i][j]]);
            }
        }
        else 
        {//否则就是没有任务，为空闲时间
            fx[i] = fx[i + 1] + 1;
        }
    }
    cout << fx[1] << endl;
    return 0;
}