题解 P1868 【饥饿的奶牛】

· · 题解

这道题其实就是客户调查的升级版

数据小的只要对客户调查的dp方程稍作修改即可

但很明显,复杂度为O(n^2)

所以不能按客户调查写;

那么,我们不能按n写,但可以按x,y写

我们用fi表示到i能吃的, 那么显然,牛只能吃或者不吃

不吃就是上一次的值, 吃就是找所有能吃的中最大的 (待会重点讲解)

不吃,很简单fi=fi-1 吃,(这里有想到dpxy的人,但实现方法千差万别,所以重点讲解一下我的方法)

首先要找到它最后一个能吃的,(当然,当有多个槽满足时需要每个都判一遍)

然后找到它能吃的最好的槽(当然也有可能还是不吃好)

所以fi=max(fi-1,fi,fp.s-1+p.e-p.s+1)(p.s,p.e表示槽的左右端点)

再讲一下如何找到最后一个能吃的

其实很简单,一个一个枚举就好啦,但要记一下上次枚举到哪,这次从它开始

敝蒟蒻不推荐二分,右端点很迷,控制不好就是t,而且一般数据还是比较密的,所以线性枚举效率不比二分低

上代码

#include<bits/stdc++.h>
using namespace std;
struct cow
{
    int s=0,e=0;
}p[1111111];
int n,f[11111111],m=0;
bool cmp(cow a,cow b)
{
    if(a.e==b.e) return a.s<b.s;
    else return a.e<b.e;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>p[i].s>>p[i].e;
        m=max(m,p[i].e);
    }
    sort(p+1,p+1+n,cmp);//排序自然是不可少的
    p[n+1].e=1e9;//为了防止while出pn+1=0这种狗屎情况而无线循环,我们人为让pn+1比所有p都大
  //  cout<<m<<endl;
    int last=0;
    for(int i=p[1].e;i<=m;i++)
    {
        int j=last,k=1;  //注意记录
        while(p[j].e<=i)
        {
            j++;    
            if(p[j-1].e==p[j].e) k++;//找有多少个末尾一样的槽
        }
        j--;
        last=j;
    //    cout<<j<<"   ";
        if(j)
            for(;k>=1;j--,k--)
            {
                int l=p[j].e-p[j].s+1;
                f[i]=max(f[i],f[i-1]);
            f[i]=max(f[i],f[p[j].s-1]+l);  //dp所有末尾一样的槽
        //    printf("%d %d %d\n",i,p[j].s,f[i]);
              ^##注释防伪标记**^
            }
    }
    cout<<f[m];
}