P1280 尼克的任务

· · 个人记录

没有采用其他题解中按时间来dp的方法，还是传统的按任务来dp。显然每个任务是一个区间，区间不能重叠是基础，同时两个区间可以形成dp关系，必须要求区间之间的区域不能有其他的区间存在。

dp[i]表示当我们执行第i个任务时可获得的最大的休息时间。注意dp数组应初始化为负无穷。

算法步骤: （1）先读入数据，并更改成区间形式，按区间左端点排序。另外用一个桶来记录每个时间点是否有区间的左端点存在。

（2）对第一个可能的任务进行dp初始化，显然只有时间最早的若干个任务可以作为dp的起点。

（3）从第二个任务开始dp。dp条件:前面的任务结束时间早于i任务开始时间，同时利用桶的前缀和数组判断这两个时间点间是否有其他任务，如果两个条件都满足则可以dp。 for(i=2; i<=k; i++) for(j=i-1; j>=1; j--) if(a[j].r<a[i].l&&sum[a[i].l-1]-sum[a[j].r]==0) dp[i]=max(dp[i],dp[j]+a[i].l-a[j].r-1);

（4）枚举最后一个任务计算最大休息时间，最后一个任务结束后（如样例）可能还有剩余时间。

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int n,k,dp[10005],sum[10005],ans;
struct node
{
    int l,r;
    bool operator<(const node y)const
    {
        return l<y.l;
    }
} a[10005];
int main()
{
    int i,j;
    memset(dp,-127/3,sizeof(dp));
    cin>>n>>k;
    for(i=1; i<=k; i++)
    {
        cin>>a[i].l>>a[i].r;
        a[i].r=a[i].l+a[i].r-1;
        sum[a[i].l]++;
    }
    for(i=1; i<=n; i++)
        sum[i]=sum[i-1]+sum[i];
    sort(a+1,a+k+1);
    for(i=1; i<=k; i++)
        if(i==1||a[i].l==a[1].l)
            dp[i]=a[1].l-1;
    for(i=2; i<=k; i++)
        for(j=i-1; j>=1; j--)
            if(a[j].r<a[i].l&&sum[a[i].l-1]-sum[a[j].r]==0)
                dp[i]=max(dp[i],dp[j]+a[i].l-a[j].r-1);

    for(i=1; i<=k; i++)
        if(sum[n]-sum[a[i].r]==0)
            ans=max(ans,dp[i]+n-a[i].r);
    cout<<ans;
    return 0;
}