题解 P1868 【饥饿的奶牛】

MichaelYoung · 2019-09-01 19:56:51 · 题解

其实这道题与尼克的任务一模一样（倒推）

设f[i]表示从第i片草地到最后一片草地能吃到的最大价值。若第i片草地是一个区间的起始，那么，此时的f[i]就是f[j]+len和f[i-1]中较大的那一个。（吃或不吃这片区间）。最后答案是f[1].

code:

#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=3000000+5;
int rec[maxn];
int len[maxn];
int Right[maxn];
int f[maxn];
int main()
{
    int n;
    scanf("%d",&n);
    int lim=0;
    for(int i=1;i<=n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        rec[x]=1;
        len[x]=y-x+1;
        Right[x]=y;
        lim=max(lim,y);
    }
    for(int i=lim;i;i--)
    {
        if(len[i])
        {
            f[i]=max(f[i+1],f[Right[i]+1]+len[i]);
        }
        else f[i]=f[i+1];
    }
    printf("%d",f[1]);
    return 0;
}