【题解】洛谷P1280尼克的任务 线性DP

题目链接

设 $f[i]$f[i] 表示 以 $i$i 时间开始的最长休息时间。
$f[i]_{i=n\to 1}=\begin{cases}\max\{f[i],f[p[x]+t[x]-1]\}\quad \exists x\in[1,k],p[x]=i\\f[i+1]+1\quad \forall x\in[1,k],p[x]\neq i\end{cases}$f[i]i=n→1​={max{f[i],f[p[x]+t[x]−1]}∃x∈[1,k],p[x]=if[i+1]+1∀x∈[1,k],p[x]̸​=i​
初值 $f[n+1]=0$f[n+1]=0 目标 $f[1]$f[1]

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=10010;
int now,f[N],n,k;
struct node{
	int p,t;
	bool operator<(const node&rhs)const{
	return p<rhs.p;}
}w[N];
int main()
{
	//freopen("in.txt","r",stdin);
	scanf("%d%d",&n,&k);now=k;
	for(int i=1;i<=k;i++)
	    scanf("%d%d",&w[i].p,&w[i].t);
    sort(w+1,w+k+1);
    for(int i=n;i;i--)
    {
    	bool free=1;
    	while(w[now].p==i)f[i]=max(f[i],f[i+w[now--].t]),free=0;
    	if(free)f[i]=f[i+1]+1;
	}
	printf("%d\n",f[1]);
	return 0;
}

总结

无