[DP] 尼克的任务 P1280 洛谷

https://www.luogu.org/problemnew/show/P1280
f[i]表示1到i个时间最大空闲值。

本题是一道资源分配类动态规划。我们可以划分阶段的标准是时间和任务。如果尼克在一个时间点上没有接到任务，我们就让他延续他原来的空闲时段，现在空闲时间=上一个空闲点的空闲时间+1；如果这时有这个时间点开始的任务，我们就将其插入，有多个这样的任务供我们选择最优的。因为这个时间点尼克只有两个选择要么完成一个任务要么什么都不干，以开始时间来选择每一次都可以找到一个最优的。但是本题好在开始时间和完成时间都有一个严格的限定，所以我们可以不用考虑一个任务插入在哪个时间结束，只要根据开始时间和结束时间进行插入控制就行了。

（本时刻无任务）f[i]=f[i+1]+1;//继承上一个时刻的最大空闲时间后+1
（本时刻有任务）f[i]=max(f[i],f[i+a[sum])//a[sum]表示在这个时刻的任务的持续时间，找出选择哪一个本时刻任务使空闲时间最大化

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <list> 
using namespace std;
typedef long long ll;

const int maxn = 10000+5 ;
const int maxv = 10000+5;
const int mod = 1000000 ;
const int INF = 0x3f3f3f3f;
const double PI=acos(-1.0);

int n,m,d,x,y,flag;
pair<int,int> a[maxn];
int tims[maxn];
int dp[maxn];

bool cmp(pair<int,int> a,pair<int,int> b){
    return a.first>b.first;
}

int main(){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++) scanf("%d %d",&a[i].first,&a[i].second),tims[a[i].first]++;
    sort(a+1,a+1+m,cmp);// times 存这个时间有几个任务开始
    int cnt=1;
    for(int i=n;i>=1;i--){ // 有后效性 我们倒着来
    	if(tims[i]==0) dp[i]=dp[i+1]+1;
    	else for(int j=1;j<=tims[i];j++){ // 有工作必须选一个 显然早 后面转态让我和空闲和最大比较好 
    		dp[i]=max(dp[i],dp[i+a[cnt++].second]);
        }
    }
    cout<<dp[1]<<endl;
    return 0;
}