线性DP
思路
见 : https://www.luogu.com.cn/blog/zhy137036/solution-p1868
代码
#include<bits/stdc++.h>
using namespace std;
const int N=3e6+10;
int f[N],n;
vector<int> a[N];
int main()
{
cin>>n;
int length=INT_MIN;
for(int i=1;i<=n;i++)
{
int x,y;
cin>>x>>y;
a[y].push_back(x-1);
length=max(length,y);
}
for(int i=1;i<=length;i++)
{
f[i]=f[i-1];
for(int j=0;j<a[i].size();j++)
f[i]=max(f[i],f[a[i][j]]+i-a[i][j]);
}
cout<<f[length]<<endl;
return 0;
}