P1868 【饥饿的奶牛】

波风一一水门 · 2021-10-26 17:45:55 · 个人记录

线性DP：

题目描述：

给定 n 个区间（任务），任意选择一些区间，使得区间不能重叠，求最大的区间长度和。n=1e5，3e6>=区间端点>=0。

思路：

先贪心一下发现不行，就考虑DP。

题目分析：

对于一个区间来说可以根据选与不选划分，很容易想到可以枚举时间轴，因为这样方便状态转移，如果枚举第i个区间的话不容易找到前一个状态，所以显然要用时间轴，利用差值来转移状态。

状态表示：

f[i]当前时刻为i，从前往后选择区间所得到的最大区间和。

状态转移：

如果当前这个时刻不是某个任务的结尾时刻：

显然状态转移就是 f [ i ] = f [i - 1]。

如果当前这个时刻是某个任务的结尾时刻：

显然状态转移就是 f [ i ] = f [i - len] + len , len为这个任务的持续时间，同时也是选择这个区间的收益。

实现：

代码实现起来可以用二维vector存当前某个时刻为终点的所有区间，但是因为区间长度是3e6，很多编译器可能编译不了。所以开一个固定空间的数组是不稳定的。这里可以用链表实现。

时间复杂度：

总共的区间一共是1e5个，我们遍历时间轴，不论一个右端点有多少个左端点，总共的遍历的区间个数仍是1e5个，时间复杂度是严格O(n)

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=3e6+10;
int f[N],ne[N],h[N],w[N],e[N],idx;
void add(int a,int b,int c)
{
    e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
signed main()
{
    memset(h, -1, sizeof h);
    int n;
    int maxlen=3e6+1;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int x,y;
        cin>>x>>y;
        add(y,x,y-x+1);//以y结尾的的区间，长度为y-x+1
    }
    for(int k=0;k<=maxlen;k++)//扫描整个区间
    {
        f[k]=f[k-1];
        for(int i=h[k];~i;i=ne[i])
        {
            f[k]=max(f[k],f[k-w[i]]+w[i]);
        }
    }
    cout<<f[maxlen]<<endl;
}