先考虑从左往右跳

$dp_{i,j}$ 表示由 $x_j$ 位置到达 $x_i$ 位 $dp_{i,j}=\max_{x_i-x_j\ge x_j-x_k,k<j,j<i}\{dp_{j,k}\}+p_i$ $dp_{i,j}=\max_{x_i\ge 2\times x_j-x_k,k<j<i}\{dp_{j,k}\}+p_i$

由此固定 $i$ ，每次 $j$ 增大都影响 $k$ 的范围，进行单调队列优化维护 $dp_{j,k}$ 最大值，最后答案 $\max_{i=1}^n\max_{j=1}^i dp_{i,j}$ 正确吗？

不知道是正确性有问题还是我写挂了

for(int i=1;i<=n;i++){
		int k=1;
		for(int j=1;j<i;j++){
			for( ;k<j;k++){
				while(q.size() && dp[j][q.back()]<=dp[j][k]) 
					q.pop_back();
				q.push_back(k);
			}
			while(q.size() && x[i]<2*x[j]-x[q.front()]) q.pop_front();
			if(q.size()) dp[i][j]=dp[j][q.front()]+a[i];
		}
	}