题解 P1868 【饥饿的奶牛】

mzgwty · 2019-04-09 13:14:23 · 题解

表示蒟蒻完全没有想出来线性怎么做

膜一下写出O(n)算法的dalao

方程很简单

f[i]表示前i个区间能选到的最大数量

f[i]=max(f[i-1],f[j]+a[i].tail-a[i].head+1);//j表示尾小于当前区间头且f最大的区间下标

这个DP其实是个n^2算法，肯定过不了。

于是看有找尾小于当前头的一重O(n)的循环，就考虑利用二分查找优化一下，所以就要先按尾从小到大排序，然后再来dp

inline int lower_bound(int l,int r,int key) {
    int ans=0;
    while(l<=r) {
        int mid=(l+r)>>1;
        if(a[mid].tail<key) ans=mid,l=mid+1;
        else r=mid-1;
    }
    return ans;
}

dp方程
f[i]=max(f[i-1],f[lower_bound(1,i-1,a[i].head)]+a[i].tail-a[i].head+1);

于是就有了题解中最慢的代码(不确定吧)

#include<bits/stdc++.h>
using namespace std;

struct unit {
    int head,tail,val;
}a[150005];

int n;

int f[150005];

inline bool cmp(unit a,unit b) {
    return a.tail<b.tail;
}

inline int lower_bound(int l,int r,int key) {
    int ans=0;
    while(l<=r) {
        int mid=(l+r)>>1;
        if(a[mid].tail<key) ans=mid,l=mid+1;
        else r=mid-1;
    }
    return ans;
}

int main() {
    scanf("%d",&n);
    for(register int i=1 ; i<=n ; ++i) {
        scanf("%d%d",&a[i].head,&a[i].tail);
        a[i].val=a[i].tail-a[i].head+1;
    }
    sort(a+1,a+n+1,cmp);
    for(register int i=1 ; i<=n ; ++i) {
        f[i]=max(f[i-1],f[lower_bound(1,i-1,a[i].head)]+a[i].val);
    }
    printf("%d",f[n]);
    return ~~(0^0);
}