dp[i]:从第i分钟开始到第N分钟的最大空闲时间.
当第i分钟无开始的任务,dp[i]=dp[i+1]+1;
否则,dp[i]=max{ dp[ i+t[j] ] }, t[j]为第i分钟开始的任务的持续时间.
然后逆推…
关于顺推的尝试(dp[i]:从第1分钟开始到第i分钟的最大空闲时间):
如果将结束时间排下序,然后顺推,就不行,因为不一定会选择在该时刻结束的任务.
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
int dp[10005];
struct T{
int p,t;
bool operator< (const T &a){
return p<a.p;
}
}a[10005];
int main(){
int n,k;
cin>>n>>k;
for(int i=0;i<k;++i){
cin>>a[i].p>>a[i].t;
}
sort(a,a+k);
for(int i=n,j=k-1;i>=1;--i){
if(i!=a[j].p){
dp[i]=dp[i+1]+1;
}
else{
while(j>=0&&i==a[j].p){
dp[i]=max(dp[i+a[j].t],dp[i]);
j--;
}
}
}
cout<<dp[1]<<endl;
return 0;
}