luoguoj–p1280–nick’s tasks

Problem URL:Nick’s Problem

It is obviously a Dynamic Programming Problem.The status transition function is :

f[i]=max(f[i],f[i]+task[j,i]) if(task[j][0]==i) ->If i moment have task
f[i]=f[i-1]+1 if(task[j][0]!=i) -> If i moment doesn’t have task

f[i]:The maximum break time Nick can get at time i;
task[i][0/1]:the start time and end time of the i th task.

initially,f[i]=0,task[i][j]=0;

Source code shows blow:

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int MAXN = 100001;

int task[MAXN][2];
int ans[MAXN];
void init(){
    memset(task,0,sizeof(task));
    memset(ans,0,sizeof(ans));
}
int main(){
    init();
    int tot,n;
    cin>>tot>>n;
    for(int i=1;i<=n;i++){
        cin>>task[i][0]>>task[i][1];
    }
    bool haveTask;
    for(int i=tot;i>=1;i--){
        haveTask=false;
        for(int j=1;j<=n;j++){
            if(task[j][0]==i){
                haveTask=true;
                ans[i]=max(ans[i],ans[i+task[j][1]]);
            }
        }
        if(!haveTask){
            ans[i]=ans[i+1]+1;
        }
    }
    cout<<ans[1];
    return 0;
}