我们注意到，这道题要求小球最大价值和，并且即使权值变为负的也要算上。因此，状态转移时只要维护所有小球损失的价值“最小即可。
这是一道典型的区间dp,因此我们可以设值状态为\(dp(i,j,pos)\),其中\(pos\)表示Sue在区间\([i,j]\)的左端还是右端。为什么要有这个状态呢？由于移动需要时间，需要分类讨论sue的位置。
其次，为什么可以表示成区间
\(s[i,j]\)呢？可以自行画图发现，Sue所经过的区间一定是一个连续区间，区间内的所有小球都被收集。
第三是状态的定义。按照传统思路，我们把它定义为“已经过区间\([i,j]\),在\(pos\)端，所区间内损失的价值”，但会在转移时出现一些问题：①每到收集一个小球，我们就要更新状态，这就要求我们记录每个状态用时；②Sue在收集小球时，所有未收集的球都在下落，但我们没有考虑这些球的损失，从而可能出现前期因追求最优解而耽误时间，后期损失极大“，不能取到最优解。因此，我们改变定义为“目前所有小球损失之和，"从而可以取到最优解。
第四是状态的转移存在性，首先，
\([i,j]\)指的是"第i~j个小球",而不是\(x\)坐标，用离散化来压缩状态数量。其次，由于题目给定了出发点\(x_0\)。因此次，由于题目给定了出发点\(x_0\)，因此\(x_0\)不包含在\([i,j]\)里的状态都没有用，预处理为∞。另外，为方便转移，要把出发点视为一个{\(x_0\),\(0\),\(0\)}的小球。
第五是状态转移，以\(dp(i,j,0)\)为例。由于\(i\)是新收集的小球（\(pos\)为\(0\),Sue在\(i\)上）,状态一定由\([i+1,j]\)转移来。依次考虑\(pos\)为\(0\)和\(1\)的情况，并更新在路程中，未收集的小球掉落所产生的损失。由此方程为
\(dp(i,j,0)\) =
\(min\){\(dp(i,j,0)\)+( \(x_r\)-\(x_i\))*($\sum_{k = 0}^{n} \ v_k $ - $\sum_{k = i+1}^{j} \ v_k \() ,
\)dp(i+1,j,1)\(+(\)x_j\(-\)x_i\()*(\)\sum_{k = 0}^{n} \ v_k - \sum_{k = i+1}^{j} \ v_k \()}
反之亦然。（注：r=i+1)
因此，输出答案为
\)-min\({\)dp(0,n,0),dp(0,n,1)\(}另外要注意两点，
第一，方程中的\)segma\(部分可以用前缀和优化
第二，小球有\)n\(个，那为什么有
\)dp(0,n,0)$呢？因为我们又加了一个虚拟的出发点的小球。
就这样解决了本题。
附AC代码：