题解 P1280 【尼克的任务】

· · 题解

逛了一圈题解发现并没有我的思路qvq（虽然我的想法不仅丑陋难写常数大还是nlogn的复杂度

很明显是个DP了emmmm但是我没想到倒序转移这么NB的东西

令dp[i]表示完成前i个任务的总休息时间，如果起点为a[i].x，终点为a[i].y,那么当前值一定是由

从起始时间往前数直到另一个任务的起始时间

在这段区间里结尾的i的dp值转移过来

我们考虑以左端点排序，这样预处理出每段区间。暴力转移是n方的，估计也能过，但是我们考虑优化。

维护一课权值线段树，初值为-inf，在a[i].y的位置上存储dp[i]-a[i].y的值，维护区间最大值，这样我们转移的时候就可以直接寻找区间最大值加上当前左端点，像这样

dp[i]=query(1,1,10000,a[i].last+1,a[i].x)+a[i].x;

因为很明显a[i].x-a[j].y即为休息时间，这样就每次找到最大值。

细节还是很多的，具体见代码

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

inline int read() {
    int x=0,f=1;
    char cr=getchar();
    while (cr>'9' || cr<'0') {
        if (cr=='-') f=-1;
        cr=getchar();
    }
    while (cr>='0' && cr<='9') {
        x=(x<<3)+(x<<1)+cr-'0';
        cr=getchar();
    }
    return x*f;
}

const int maxn=10050;

struct node{
    int x,y;
    int last;
}a[maxn];

inline bool cmp1(node a,node b) {
    if (a.x==b.x) return a.y<b.y;
    return a.x<b.x;
}

int tr[maxn<<2];
int dp[maxn];

inline void add(int now,int l,int r,int loc,int val) {
    if (l==r) {
        tr[now]=max(tr[now],val);
        return;
    }
    int mid=l+r>>1;
    if (loc<=mid) add(now<<1,l,mid,loc,val);
    else add(now<<1|1,mid+1,r,loc,val);
    tr[now]=max(tr[now<<1],tr[now<<1|1]);
}

inline int query(int now,int l,int r,int x,int y) {
    if (x<=l && r<=y) return tr[now];
    int ans=-2e9,mid=l+r>>1;
    if (x<=mid) ans=max(ans,query(now<<1,l,mid,x,y));
    if (mid+1<=y) ans=max(ans,query(now<<1|1,mid+1,r,x,y));
    return ans;
}

int main() {
    int n=read(),k=read();
    n++;
    memset(tr,-0x3f,sizeof(tr));
    memset(dp,-0x3f,sizeof(dp));
    int mx=0;
    for (int i=1;i<=k;i++) {
        a[i].x=read(),a[i].y=a[i].x+read();
        mx=max(mx,a[i].x);
    }
    sort(a+1,a+k+1,cmp1);
    int cnt=1;dp[1]=a[1].x-1;
    add(1,1,10000,a[1].y,dp[1]-a[1].y);
    while (a[++cnt].x==a[1].x) {
        dp[cnt]=a[cnt].x-1;
        add(1,1,10000,a[cnt].y,dp[cnt]-a[cnt].y);
    }
    for (int i=1;i<=k;i++) {
        if (a[i].x!=a[i-1].x) a[i].last=a[i-1].x;
        else a[i].last=a[i-1].last;
    }
    int ans=0;
    for (int i=cnt;i<=k;i++) {
        dp[i]=query(1,1,10000,a[i].last+1,a[i].x)+a[i].x;
        add(1,1,10000,a[i].y,dp[i]-a[i].y);
        if (a[i].y>mx) ans=max(ans,dp[i]+(n-a[i].y));
    }
    printf("%d",ans);
}