rt ,我跟我看到的题解状态设的都不一样,请问f[i]表示前i个区间最多能吃到的牧草堆数这个状态可以吗?还是我想错了?
#include<bits/stdc++.h>
using namespace std;
const int N=3e6+1;
int n,f[N];
struct Node{
int l,r;
}a[N];
bool cmp(Node x,Node y){
if(x.l!=y.l) return x.l<y.l;
else return x.r<y.r;
}
int main(){
int ans=0;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d%d",&a[i].l,&a[i].r);
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;i++){
f[i]=f[i-1]+(a[i-1].r>=a[i].l?0:a[i].r-a[i].l+1);
int j=i-1;
while(a[j].r>=a[i].l){
j--;
f[i]=max(f[i],f[j]+a[i].r-a[i].l+1);
}
ans=max(ans,f[i]);
}
printf("%d",ans);
return 0;
}