CF1068D
呃这题真的搞了好久啊，理解能力变差了。
我们假设我们最大可以走到的下标是 \(x_i\)，最小可以走到的下标是 \(x_j\)。那么答案就是 \(x_i-x_j+1\)。
而我们发现这个下标一定是累计得到的，就比如第 \(3\) 时刻的下标一定是 \(a_1+a_2+a_3\)，也就是前缀和。所以在不考虑往 \(0\) 的地方填数的情况下，答案就是 \(\max\{\max\{s\}-\min\{s\}+1\}\)。
回到我们一开的假设，根据那个假设，我们可以把这只狗行走的部分分成三段。我们不妨设这只狗先走到最小的下标再走到最大的下标，反之亦然。
-
第一部分，\([1,x_{i-1}]\) 。这一段是这只狗从起点走到最小的下标的过程。
-
第二部分，\([1,x_j]\) 。这一段是这只狗从起点最大的下标的过程。
-
第三部分，\([1,n]\) 。这一段是这只狗经过了前面一系列移动最后又回到零点的过程。
那么我们发现，真正影响答案的就是 \([x_{i-1},x_j]\)。这一部分向扩展的越多，那么我们答案也就越大。
考虑到 \(n\le 3000\) ，那我们不妨 \(O(n^2)\) 枚举 \(x_i\) 和 \(x_j\) 。
我们假设当前这段区间 \([x_i,x_j]\) 已知能扩展的和是 \(\text{sum}\)，\(0\) 的个数是 \(\text{zero}\) 那么这段区间最多能扩展到的地方是 \(\text{sum}+\text{zero}\times k\) 。
但我们必须要明白一点，就是我们扩展到了最大值有些时候是无法回到零点的。所以我们同时也要算出这段区间外的两个区间总共走了多少，给我们留下了多少的走动空间，
我们不妨调整一下顺序，把 \([x_{i-1},x_j]\) 单独考虑。剩下两断合并到一起走，这样显然不影响结果。
那我们同样假设这两段已经扩展的和是 \(\text{sum}\)，\(0\) 的个数是 \(\text{zero}\)。
那么这一段留给 \([x_{i-1},x_j]\) 空余能走的地方是 \(\text{sum}-\text{zero}\times k\) 。至于为什么这里是减号，还记得我们一开始做的假设吗？我们设这只狗先走到最小的下标再走到最大的下标，所以 \([x_{i-1},x_j]\) 这一段一定是全部向右走，所以剩下两断区间合并起来就是全部向左走，因为最后要回到 \(0\) 。
最后说一下无解的判断，如果这个数列 \(|s_n|\) 的和大于零的个数乘以 \(k\) 的话，那么必然无解，因为这样就算零的部分全填 \(k\) （或 \(-k\)），都无法达到
\(|s_n|\)。
看看关键代码。
//sum 就是前缀和数组，d 是零的个数
int tmp=sum[r]-sum[l-1];int cnt=d[r]-d[l-1];//这个是算[x_{i-1},x_j] 这个区间的和以及0的个数
int tmpp=sum[n]-tmp;int cntt=d[n]-cnt;//剩下两个区间
ans=max(ans,min(abs(tmp+cnt*k),abs(tmpp-cntt*k)));//先走到最小值再走到最大值
ans=max(ans,min(abs(tmp-cnt*k),abs(tmpp+cntt*k)));//先走到最大值再走到最小值