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];
}
标签:int,MAX,任务,休息时间,尼克,dp,define From: https://www.cnblogs.com/Wang-Xianyi/p/16638650.html