banner

原题链接

https://www.luogu.com.cn/problem/P1280

解题思路

动态规划，具体步骤如下。

  • 预处理阶段
    设置两个bool数组begin、end，begin数组记录每个时间点有无任务开始，end数组记录每个时间点有无任务结束。每次输入一个任务的起止时间后，更新两个bool数组并建立一条从终止时间到起止时间的有向边，用vector实现的二维数组存储。

  • DP阶段
    从后往前进行一遍扫描。设置数组f，f[i]记录从时间点i到工作日结束之间最长的空暇时间（即：时间点i的“逆推最大空暇时间”）。

扫描到有任务结束的时间点时，以为此时任务刚结束，从下一分钟才会进入空暇状态，故我们用当前时间下一分钟的“逆推最大空暇时间”分别对【当前时间结束的所有任务】的起始时间的“逆推最大空暇时间”进行比较，若更大则替换之。这一步把所有有任务开始的时间点的“逆推最大空暇时间”已经更新为最优解。

同时，若没有任务在当前时间开始，则下一分钟的“逆推最大空暇时间”加一之后即为当前时间的“逆推最大空暇时间”。

一遍扫描过后，f[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
#include<cstdio>
#include<vector>
using namespace std;
int n,k,t,p,now,f[10001];
bool begin[10001],end[10001];
vector<int> v[10001];
int max(int x,int y){return x>y?x:y;}
int main()
{
  scanf("%d%d",&n,&k);
  for(int i=1;i<=k;i++)//预处理阶段
    {
      scanf("%d%d",&p,&t);
      begin[p]=1;//做标记
      end[p+t-1]=1;
      v[p+t-1].push_back(p);//建边
    }
  for(int i=n;i>=1;i--)//DP阶段
    {
      if(end[i])
    for(int k=0;k<v[i].size();k++)
      f[v[i][k]]=max(f[v[i][k]],f[i+1]);
      if(!begin[i])f[i]=f[i+1]+1;
    }
  printf("%d",f[1]);
  return 0;
}