f[i]表示i~n的最长空闲时间；
如果当前无任务就休息一秒（f[i]=f[i+1]+1）；
否则f[i]=max(f[i],f[i+当前工作时间]);
用结构体来记录，我们对于每一个时刻开一个数组来存以此时刻为起始点的所有任务，下标0来表示数组中的元素个数，便于遍历：
#include<iostream>//简短的30行代码 #include<cstdio> #include<algorithm> #include<cstdio> using namespace std; int n,k,f[10010]; struct cym{ int num[10010]; }a[10010]; int main() { scanf("%d%d",&n,&k); for(int i=1;i<=k;i++) { int x,y; scanf("%d%d",&x,&y); a[x].num[++a[x].num[0]]=y; } for(int i=n;i>=0;i--) { if(!a[i].num[0]) { f[i]=f[i+1]+1; continue; } for(int j=1;j<=a[i].num[0];j++) f[i]=max(f[i],f[i+a[i].num[j]]); } printf("%d",f[1]); }
原文：https://www.cnblogs.com/zzh666/p/9005206.html