题解 P1868 【饥饿的奶牛】

我用了楼下的dp方程终于做出了这题。 难啊，我来发个题解纪念一下我通过的第一道浅蓝色题目 不过，其实就是找最右的端点，然后从0一直找过去，每次都对该点求最好的吃的方法，最后ans找最大值。 也许你觉得我抄楼下的，其实我的确用了楼下的dp方程，但是我加了优化。 不说了上代码。 ```cpp #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; } ```