P1280 尼克的任务

本题链接：P1280 尼克的任务

本博客给出本题截图：

AC代码

代码解析：
f[i]代表的是从i ~ n中最长可以休息的时间，对于一个节点i而言，如果i这个时刻没有工作，那么有：f[i] = f[i + 1] + 1，如果有工作的话，那么有：f[i] = max(f[i], f[i + v[i][j]])

代码：

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 10010;

vector<int> v[N];
int f[N];
int n, k;

int main()
{
	cin >> n >> k;
	for (int i = 1; i <= k; i ++ )
	{
		int p, t;
		cin >> p >> t;
		v[p].push_back(t);
	}
	
	for (int i = n; i; i -- )
	{
		if (v[i].empty()) f[i] = f[i + 1] + 1;
		else
		{
			for (int j = 0; j < v[i].size(); j ++ )
				f[i] = max(f[i], f[i + v[i][j]]);
		}
	}
	
	cout << f[1] << endl;
	
	return 0;
}

  

 

  
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
  
34
  
35
  
36
 

文章来源: chen-ac.blog.csdn.net，作者：辰chen，版权归原作者所有，如需转载，请联系作者。

原文链接：chen-ac.blog.csdn.net/article/details/119832253