P1868 饥饿的奶牛 线性DP

· · 个人记录

题目简介

https://www.luogu.com.cn/problem/P1868

思路

这是一道区间问题，基本思路有两种，一种是以位置为阶段，一种是以每个区间为阶段。

最容易想到的方法是以区间为阶段。

首先对每个区间进行排序，这里是以结尾升序排列。

然后是状态： dp[i] 表示前 i 个区间取的最大值。

接着想想怎么得到 dp[i] ，不妨设第 j 个区间的末尾小于第 i 个区间的开头，则 dp[i] 可以由 dp[j] 得到。

这样做乍一看时间复杂度是 n^2 ，但可以优化。

由于已经对结尾进行了升序排列，且 dp[i] 的定义是前 i 个区间的最大值。

因此，只需利用二分查找，找到第一个满足条件的 j 。

再次提一下 dp[i] 的定义，上述方式是取第 i 个区间得到的最大值，可能不取它所得到值更大，所以需要对两种情况取最大值。

这样时间复杂度变为 nlogn 。

附上代码：

#include<bits/stdc++.h>
using namespace std;
struct hh
{
    long long x,y,s;
}a[200005];
long long n,dp[200005]; 
bool cmp(hh a,hh b) {return a.y<b.y;}
int erf(int p)
{
    int l=0,r=p,mid;
    while(l+1<r)
    {
        mid=(l+r)>>1;
        if(a[mid].y<a[p].x) l=mid;
        else r=mid;
    }
    return l;
}
int main()
{
    cin>>n;
    for(int i=1; i<=n;i++) 
    {
        scanf("%lld%lld",&a[i].x,&a[i].y);
        a[i].s=a[i].y-a[i].x+1;
    }
    sort(a+1,a+1+n,cmp);
    for(int i=1; i<=n;i++)
    {
        dp[i]=max(dp[i-1],dp[erf(i)]+a[i].s);
    }
    cout<<dp[n];
    return 0;
 }

总结

区间问题可以令区间为阶段，也可以令位置为阶段，哪个好做用哪个。

对于一些 DP 问题，可以考虑二分优化。