洛谷P1280 尼克的任务

洛谷P1280 尼克的任务

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;
}