P1868 饥饿的奶牛

点击查看代码

#include<bits/stdc++.h>
using namespace std;const int N=2e5,M=3e6+10;
vector<int> starts[M];
int n;
int f[M];int main()
{ios::sync_with_stdio(0),cin.tie(0);cin>>n;int max_r=-2e9;//整体平移加+1，因为状态转移要用到x-1，防止越界for(int i=1;i<=n;i++){int x,y;cin>>x>>y;++x,++y;starts[y].push_back(x);max_r=max(y,max_r);}for(int i=1;i<=max_r;i++){f[i]=f[i-1];for(auto& l : starts[i]){f[i]=max(f[i],f[l-1]+i-l+1);}}cout<<f[max_r]<<"\n";return 0;
}