题目链接
分析： 这道题很久以前（一年前???） 就做过了，但是直到现在我也并不觉得简单
如果我们选择完成一项工作 那么最长休息时间就要看完成之后的状态
f[i]=f[i+job[j].t]
dp的原则是当前状态一定要由稳定状态转移来 那么明显要从后向前循环
那如果当前没有任务怎么办呢
f[i]=f[i+1]+1;
状态分析完毕~
这里写代码片 #include<cstdio> #include<iostream> #include<cstring> #include<algorithm> using namespace std; const int N=10010; struct node{ int s,t; }; node job[N]; int n,m,f[N]; int cmp(const node &a,const node &b) { if (a.s!=b.s) return a.s<b.s; else return a.t<b.t; } void doit() { int i,j=m; for (i=n;i>=1;i--) { if (job[j].s!=i) f[i]=max(f[i],f[i+1]+1); while (job[j].s==i) { f[i]=max(f[i],f[i+job[j].t]); j--; } } printf("%d",f[1]); } int main() { scanf("%d%d",&n,&m); for (int i=1;i<=m;i++) scanf("%d%d",&job[i].s,&job[i].t); sort(job+1,job+1+m,cmp); doit(); return 0; }