尼克的任务

P1280 尼克的任务 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

• 如果当前时间没有任务，那么当前的最大休闲时间就是下一个时刻的最大休息时间,即dp[i]=dp[i+1]+1
• 因为如果我们希望一时刻做的工作能够带来最多的休息时间,那么我们就必须要在工作做完的时间后找到最大的休息时间，即dp[i]=max(dp[i],dp[i+v[i][j]])
• 因为这样的递推关系是用后面的时间的最大休息时间求前面的，所以需要逆序

#include <bits/stdc++.h>
using namespace std;
#define N 1e5
#define INF 2e9
#define MAX 100005
// https://www.luogu.com.cn/problem/P1280
int n, k, s, l, dp[MAX];
vector<int> v[MAX];
int main()
{
    cin >> n >> k;
    while (k--)
        scanf("%d%d", &s, &l), v[s].push_back(l);
    for (int i = n; i; i--)
        if (v[i].empty())
            dp[i] = dp[i + 1] + 1;
        else
            for (int j = 0; j < v[i].size(); j++)
                dp[i] = max(dp[i], dp[i + v[i][j]]);
    cout << dp[1];
}