题目链接：https://www.luogu.com.cn/problem/P1280

大意，给出一个时间n和任务数  k

每个任务给出开始时间和持续时间。求最大的休闲时间。

很明显这个题是一个线性动态规划的题，但是却不好推导状态转移公式，尤其是有任务的时候，状态转移公式很难推。

解决方法：我们设 f[i] 为 1- i时刻休闲的最大时间，那么如果i时刻没有任务，我们可以得出，下一个i+1时刻的休闲时间是  max（f[i]+1,f[i+1]），也就是本身和没有任务节点+1的最值。

如果i这个时刻有任务我们应该怎么办？我们将i时刻的所有任务遍历出来，然后用这个结束后的fi休闲时间和没做这些任务时的休闲时间做一个比较。

所任务结束后的fi =  没做任务的fi，那么说明我们顺着做这个任务休闲时间更长，也就取决于没做任务时fi的休闲时间更长。长此以往。

f[i+work[i][j]] = max(f[i+work[i][j] , f[i]）fi 正是我们遍历的时刻。通过时刻遍历该时刻的任务，从而转移任务结束后的最优解。

code:

#include<bits/stdc++.h>
using namespace std;
const int nn = 1e4+10;
vector<int> work[nn]; 
int f[nn];
int main()
{
	memset(f,-0x3f,sizeof f);
	f[1] = 0;
	int n,k,p,t;
	cin>>n>>k; 
	while(k--)
	{
		cin>>p>>t;
		work[p].push_back(t);
	}
	for(int i=1;i<=n;i++)
		if(work[i].size()==0)
			f[i+1] = max(f[i]+1,f[i+1]);
		else for(int j=0;j<work[i].size();j++)//如果有工作，我们就把工作给遍历出来
				f[i+work[i][j]] = max(f[i+work[i][j]],f[i]);//看看这个工作结束后的那个时间节点的休闲时间和不做这个工作的休闲时间哪个长 
	cout<<f[n+1];
}