[luogu] P1280 尼克的任务 倒序+线性DP

前言

传送门 :

思路

用 f [ i ] f[i] f[i]表示当前的最大休闲时刻

那么如果当前没有任务的话 f [ i ] = f [ i + 1 ] + 1 f[i] = f[i+1]+1 f[i]=f[i+1]+1

否则 f [ i ] = m a x ( f [ i ] , f [ i + j ] ) f[i]=max(f[i],f[i+j]) f[i]=max(f[i],f[i+j])

CODE

void solve()
{
	cin>>n>>k;
	while(k -- )
	{
		int a,b;cin>>a>>b;
		v[a].pb(b);
	}
	
	for(int i = n;i;i -- )
	{
		if(v[i].size() > 0)
		{
			for(auto j: v[i])
			f[i] = max(f[i],f[i+j]);
		}else f[i] = f[i+1]+1;
	}
	
	cout