做起来真的没有想象中的那么难（？）感谢 @zltqwq 讲的好题/bx
首先考虑蜡烛可以烧到负数长度怎么做。发现这题等同于关路灯。设个状态：\(dp_{i,j,0/1}\) 表示当前 \([i,j]\) 范围内的蜡烛都已熄灭，现在人在左/右端点的最大答案。枚举从 \([i+1,j]\) 或 \([i,j-1]\) 转移即可。
然后加入只能烧到 \(0\) 长度怎么做。看起来变得非常麻烦，但是会发现一个性质：此时问题的答案不会比上面问题的答案更小。因为相对于上面的问题，此时长度 \(<0\) 的蜡烛相当于是被我们删去了。
此时就可以将这个问题转化一下：你可以在这些蜡烛中选任意多个删去，并根据上面的方式计算，并将所有结果取 \(\max\)。因为在最优情况中，有正贡献的蜡烛一定会被选，否则一定不会。所以这两个问题是等价的！
现在是不是就变得明朗了呢？
所以可以直接把选了多少个塞进状态。设 \(dp_{i,j,k,0/1}\) 表示当前 \([i,j]\) 范围内的蜡烛都已熄灭，还有 \(k\) 个蜡烛会产生贡献，现在人在左/右端点的最大答案。枚举从 \([i+1,j]\) 或 \([i,j-1]\) 转移及当前蜡烛有没有被删去即可。时间复杂度 \(O(n^3)\)。
code：
点击查看代码
int n,m;
ll dp[N][N][N][2];
struct node{
ll c,p;
}e[N];
inline ll cost(int l,int r,int p,int k,int op){
return max(dp[l][r][k][op]-(op?abs(e[r].p-e[p].p):abs(e[l].p-e[p].p))*k,dp[l][r][k+1][op]-(op?abs(e[r].p-e[p].p):abs(e[l].p-e[p].p))*(k+1)+e[p].c);
}
inline bool cmp(node x,node y){
return x.p!=y.p?x.p<y.p:x.c>y.c;
}
void Yorushika(){
scanf("%d",&n);
rep(i,1,n){
scanf("%lld%lld",&e[i].p,&e[i].c);
}
e[++n]={-inf,0};
sort(e+1,e+n+1,cmp);
int s=0;
rep(i,1,n){
if(!e[i].p)
s=i;
}
mems(dp,-0x3f);
rep(i,0,n){
dp[s][s][i][0]=dp[s][s][i][1]=0;
}
ll ans=0;
drep(i,s,1){
rep(j,s,n){
if(i==j)
continue;
rep(k,0,n){
dp[i][j][k][0]=max(cost(i+1,j,i,k,0),cost(i+1,j,i,k,1));
dp[i][j][k][1]=max(cost(i,j-1,j,k,0),cost(i,j-1,j,k,1));
ans=max(ans,max(dp[i][j][k][0],dp[i][j][k][1]));
}
}
}
printf("%lld\n",ans);
}
signed main(){
int t=1;
// scanf("%d",&t);
while(t--)
Yorushika();
}