luogu-P1280 尼克的任务【线性动态规划】

P1280 尼克的任务 link

思路：
我们考虑用线性动规。
设f[i]表示1~i的最大空闲时间，但是我们会发现对于当前选的工作会对后面的产生影响，不满足最优子结构。
那反过来，设f[i]表示i~n的最大空闲时间。
对于当前时间点：

1. 如果无工作开始，f[i] = f[i + 1] + 1;
2. 如果有工作开始，那我们们就判断对于当前点我们选择哪一个工作的空闲时间最大，即：f[i] = max(f[i], f[i + a[num].t]); //num表示当前点开始的工作，a[num].t表示该工作的持续时间。

因为我们是从后往前枚举，所以要按照开始时间从大到小排序。

#include 
#include 
#include 
#include 

using namespace std;

const int N = 1e4 + 10;

struct node {int p, t;} a[N];

int n, k, sum[N], f[N], num = 1;

bool cmp(node aa, node bb) {return aa.p > bb.p;}

int main()
{
	scanf("%d%d", &n, &k);
	for(int i = 1; i <= k; i++)
	{
		scanf("%d%d", &a[i].p, &a[i].t);
		sum[a[i].p]++;
	}
	sort(a + 1, a + 1 + k, cmp);
	for(int i = n; i >= 1; i--)
	{
		if(sum[i] == 0) f[i] = f[i + 1] + 1;
		else
		{
			for(int j = 1; j <= sum[i]; j++)
			{
				if(f[i + a[num].t] > f[i]) f[i] = f[i + a[num].t];
				num++;	
			}
		}
	}
	printf("%d\n", f[1]);
	return 0;
}