- 作者：zifeiy
- 标签：动态规划、最短路
题目链接：https://www.luogu.org/problem/P1280
题目大意：
有k个任务分布在第1至n这n个时间点，第i个任务的于第 \(P_i\) 分钟开始，持续时间为 \(T_i\) 分钟，则该任务将在第 \(P_i+T_i-1\) 分钟结束。
如果时刻i你是空闲的，而此时有至少一个任务是在时刻i开始的，那么你必须要在其中选择一个任务来做；
如果时刻i你是空闲的，而没有任何一个任务是在时刻i开始的，那么你在时刻i就可以是空闲的。
求你最多有多少个时刻是空闲的。
动态规划解法
我们令 \(f[i]\) 表示从时刻i开始到时刻n结束的这段时间范围内的最大空闲时刻数量。
那么我们就可以从n到1遍历时刻i，对于时刻i：
- 如果没有任务是在时刻i开始的，那么 \(f[i] = f[i+1] + 1\) ；
- 否则 \(f[i] = \max(f[ i + T_j ])\) ，其中，\(T_j\) 对应所有 \(P_j == i\) 。
实现代码如下：
#include <bits/stdc++.h>
using namespace std;
const int maxn = 10010;
int n, k, p, t, f[maxn];
vector<int> g[maxn];
int main() {
cin >> n >> k;
while (k --) {
cin >> p >> t;
g[p].push_back(t);
}
for (int i = n; i >= 0; i --) {
int sz = g[i].size();
if (sz == 0) f[i] = f[i+1] + 1;
else {
for (int j = 0; j < sz; j ++)
f[i] = max(f[i], f[ i + g[i][j] ]);
}
}
cout << f[1] << endl;
return 0;
}
最短路解法
这个思路来自 tong_xz大佬的博客
将时间点作为图中的点。
从第P分钟开始，持续时间为T分钟的任务视为从P点到P+T点连一条权为T的边。（边的起点是任务的起始时间，终点是任务结束时间的下一分钟）
如果一个点到最后也没有出度，则向后一个点连边权为0的边（没活干，这一分钟他可以摸鱼。。。）
跑最短路就得到他至少要干多长时间，答案就是（n-最短路结果）
如果将边权作为休息时间的话用最长路也能做。
实现代码如下：
#include <bits/stdc++.h>
using namespace std;
const int maxn = 10010;
int in[maxn], out[maxn], n, k, p, t, dis[maxn];
bool vis[maxn];
vector< pair<int, int> > g[maxn];
queue<int> que;
void spfa() {
memset(dis, -1, sizeof(int) * (n+2));
dis[1] = 0;
que.push(1);
while (!que.empty()) {
int u = que.front();
que.pop();
vis[u] = false;
int sz = g[u].size();
for (int i = 0; i < sz; i ++) {
int v = g[u][i].first, w = g[u][i].second;
if (dis[v] == -1 || dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
if (!vis[v]) {
vis[v] = true;
que.push(v);
}
}
}
}
}
int main() {
cin >> n >> k;
while (k --) {
cin >> p >> t;
out[p] ++;
in[p+t] ++;
g[p].push_back(make_pair(p+t, t));
}
for (int i = 1; i <= n; i ++) {
if (!out[i]) g[i].push_back(make_pair(i+1, 0));
}
spfa();
cout << n - dis[n+1] << endl;
return 0;
}