DP+贪心。
根据开始时间先后排序。
第i时刻的最大空闲时间是和后面i+选择任务的持续时间的时刻有关系的，那么，正着找肯定是不行的，我们来试一下倒着搜。
状态表示：dp[i]代表往前推到i时的最大空闲时间。
转移方程：
（1）本时刻无任务 dp[i]=dp[i+1]+1; //继承上一个时刻的最大空闲时间后+1
（2）本时刻有任务 dp[i]=max(dp[i],dp[i+a[sum]) //a[sum]表示在这个时刻的任务的持续时间，找出选择哪一个本时刻任务使空闲时间最大化
#include<bits/stdc++.h> using namespace std; const int N=10000+5; int f[N],sum[N]; struct node { int p,t; }a[N]; bool cmp(node x,node y) { return x.p>y.p; } int main() { int n,k,num=1; 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; }
原文：https://www.cnblogs.com/Siv0106/p/11722173.html