P3089
令 \(f_1[i][j]\) 表示向右跳，从 \(j\) 跳到 \(i\) 的最大总得分，有状态转移方程：
\[f_1[i][j]=\displaystyle\max_{k<j<i,x_j-x_k \le x_i-x_j}\{f_1[j][k]+s_i\}
\]
将 \(s_i\) 看作定值，整理得 \(f_1[i][j]=\displaystyle\max_{k<j<i,x_j-x_k \le x_i-x_j}\{f_1[j][k]\}+s_i\)
又因为
\[f_1[i-1][j]=\displaystyle\max_{k<j<i-1,x_j-x_k\le x_{i-1}-x_j}\{f_1[j][k]\}+s_{i-1}
\]
似乎可以代入得 \(f_1[i][j]=f_1[i-1][j]-s_{i-1}+s_i\)，但由于 \(x_{i-1}<x_i\)，所以我们要先拓展 \(k\)，然后再取最大值。
for(int j=1;j<=n;j++){
f1[j][j]=s[j];
for(int i=j+1,k=j+1;i<=n;i+++){
f1[i][j]=f1[i-1][j]-s[i-1];
while(k>1&&x[j]-x[k-1]<=x[i]-x[j]){
k--;
f1[i][j]=max(f1[i][j],f1[j][k]);
}
f1[i][j]+=s[i];
ans=max(ans,f1[i][j]);
}
}
向左跳同理，只要反着做一遍 DP 就可以了。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1009;
struct point{ll s,x;}p[N];
ll n,f1[N][N],f2[N][N],ans;
bool cmp(const point&a,const point&b){
return a.x<b.x;
}
int main(){
ios::sync_with_stdio(false);
cin>>n;
for(int i=1;i<=n;i++) cin>>p[i].x>>p[i].s;
sort(p+1,p+1+n,cmp);
for(int j=1;j<=n;j++){
f1[j][j]=p[j].s;
for(int i=j+1,k=j+1;i<=n;i++){
f1[i][j]=f1[i-1][j]-p[i-1].s;
while
(k>1&&p[j].x-p[k-1].x<=p[i].x-p[j].x){
k--;
f1[i][j]=max(f1[i][j],f1[j][k]);
}
f1[i][j]+=p[i].x;
ans=max(ans,f1[i][j]);
}
}
for(int j=n;j>=1;j++){
f2[j][j]=p[j].s;
for(int i=j-1,k=j-1;i>=1;i--){
f2[i][j]=f2[i+1][j]-p[i+1].s;
while(k<n&&p[j].x-p[k+1].x<=p[i].x-p[j].x){
k++;
f2[i][j]=max(f2[i][j],f2[j][k]);
}
f2[i][j]+=p[i].x;
ans=max(ans,f2[i][j]);
}
}
cout<<ans;
return 0;
}