Algorithm - Problem - 尼克的任务

尼克的任务 洛谷 P1280

问题描述

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

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

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

输入

输入数据第一行含两个用空格隔开的整数NNKK(1N10000,1K100001\leqslant N\leqslant 10000, 1\leqslant K\leqslant 10000),NN 表示尼克的工作时间,单位为分钟,NN 表示任务总数。
接下来共有 KK 行,每一行有两个用空格隔开的整数 PPTT,表示该任务从第 PP 分钟开始,持续时间为 TT 分钟,其中1PN,1P+T1N1\leqslant P \leqslant N, 1\leqslant P+T-1\leqslant N

输出

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

样例输入
1
2
3
4
5
6
7
15 6
1 2
1 6
4 11
8 5
8 1
11 5
样例输出
1
4

动态规划

分析

受到 UVa 1025 A Spy in the Metro 的启发,此处很自然地将时间作为序.
考虑的是反面情况,闲暇时间最大意味着工作时间最小,令 dp[T]dp[T] 表示从 TT 分钟到 NN 分钟的最少工作工作时间.
初始化时 i:1TN,dp[T]=+,dp[N+1]=0\forall i:1\leqslant T \leqslant N, dp[T] = +\infty, dp[N + 1] = 0,实际意义是超出工作日 NN 分钟时,不需要工作.
对于 dp[T]dp[T] 有如下两种情况

  1. TT 时刻有任务,去完成
  2. TT 时刻没有任务

决策分别为

  1. 分别计算待做任务的完成时刻 TT'dp[T]dp[T] 取所有 dp[T]dp[T'] 中的最小值 (取所有任务完成时刻到 NN 分钟的最少工作时间的最小值)
  2. dp[T]=dp[T+1]dp[T] = dp[T + 1]

可写为状态转移方程
dp[T]={min{dp[T+t[i]]i:p[i]=T},i:p[i]=Tdp[T+1],otherwisedp[T] = \begin{cases}\min\left\{dp[T+t[i]]\bigg|\forall i:p[i]= T\right\}, \exists i: p[i]=T\\dp[T+1], \mathrm{otherwise}\end{cases}

计算顺序为逆序,即从 TT11,最终最大的闲暇时间为 Ndp[1]N - dp[1].

代码
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
#include <iostream>
#include <cstring>
#include <algorithm>
#define MMIN(a,b) (((a)<(b))?(a):(b))
#define MAXK (10000+5)

int p[MAXK];
int t[MAXK];
int main()
{
bool flag;
int N, K;
int dp[MAXK];
std::cin >> N >> K;
for(int i = 0; i < K; i++) std::cin >> p[i] >> t[i];
dp[N + 1] = 0;
for(int i = 1; i <= N; i++) dp[i] = 100000000;
for(int T = N; T >= 1; T--)
{
flag = false;
for(int j = 0; j < K; j++)
{
if(p[j] == T)
{
flag = true;
dp[T] = MMIN(dp[T], dp[T + t[j]] + t[j]);
}
}
if(!flag) dp[T] = dp[T + 1];
}
std::cout << N - dp[1];
return 0;
}