题解 P1868 【饥饿的奶牛】

我用了楼下的dp方程终于做出了这题。

难啊，我来发个题解纪念一下我通过的第一道浅蓝色题目

不过，其实就是找最右的端点，然后从0一直找过去，每次都对该点求最好的吃的方法，最后ans找最大值。

也许你觉得我抄楼下的，其实我的确用了楼下的dp方程，但是我加了优化。

不说了上代码。

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <iomanip>
using namespace std;
int n,mx,dp[3000005],j,ans;//ans是答案，n是区间个数，j是一个下标，dp……用途如其名
struct Cow{//结构体
    int x,y,s;//x为左端点，y右，s为我的优化，即该区间的干草数
}a[150005];
inline bool cmp(Cow p,Cow q){return p.x!=q.x?p.x<q.x:p.y<q.y;}//排序
int main(){
    //freopen("P1868.in","r",stdin);
    //freopen("P1868.out","w",stdout);
    scanf ("%d",&n);
    for (int i=0;i<n;i++){
    scanf ("%d%d",&a[i].x,&a[i].y),a[i].s=a[i].y-a[i].x+1;//虽然我这个优化不大，但是我希望大家能学习这种类似于前缀和的思想
    mx=max(mx,a[i].y);//找最右端点
    }//注意！！不是排完序之后最后一个右端点就是最大的！！因为它只是左端点最大！！一定要注意！！我一开始没注意就只有73分
    sort(a,a+n,cmp);//排序
    for (int i=0;i<=mx;i++){
        dp[i]=max(dp[i],dp[i-1]);
        while (a[j].x==i&&j<n){
            dp[a[j].y]=max(dp[a[j].y],dp[a[j].x-1]+a[j].s);//dp
            j++;
        }
        ans=max(ans,dp[i]);//找最大值
    }
    printf ("%d",ans);//输出
    return 0;
}