※ 引述《DJWS (...)》之铭言：
: 推 FRAXIS: http://www.slideserve.com/xaviera-bowers/6486226 01/13 01:55
: → FRAXIS: 第八页的地方似乎就是这题..只是我看不懂他的解法.. 01/13 01:55
: 我也看不太懂，我猜是这样：
: 令a[i]=h[i]-h[i+1]
: h[i]加1 <=> a[i-1]减1 且 a[i]加1。
: h[i]减1 <=> a[i-1]加1 且 a[i]减1。
: h[i]加1，可以视作“一单位的水从a[i-1]流到a[i]”。
: h[i]减1，可以视作“一单位的水从a[i]流到a[i-1]”。
: 因此设定a[i-1]到a[i]是无向边（只能选其中一个方向流动）。
: h[i]加1或者减1，minimize的对象就加1。
: 因此该无向边费用设定成1。
: 当无向边的流量越少，则minimize的对象就越小。
: 因此设定为最小费用流。
: 若a[i]<-d，则至少要从别的地方拿个1，且不能多于|a[i]|-d个1；
: 因此从点i向t连边，容量下界|a[i]|-d，上界|a[i]|+d，费用0。
: 题目规定相邻两数差a[i]的范围是 -d ~ +d （d是正数）
: a[i]<-d 就必须把a[i]补到变成-d，至少需要补-d - a[i] = |a[i]| - d。
: 把边拉往target，是为了强迫source一定要补东西进来，
: 要从哪个入口补入都可以（每一个h[i]都可以调整）
: 设定出口的容量上下限，就能控制入口补多少东西进来。
: 大概就是这种感觉
: 然后我觉得他的source和target颠倒过来应该也OK...
我好像大概了解了，不知道有没有错..
输入为A，然后前处理计算P[i] = A[i] - A[i+1]，我们要求解B[]。
令 X[i] 为变量表示 A[i] 的增加量。
Y[i] 为变量表示 A[i] 的减少量。
所以 B[i] = A[i] + X[i] - Y[i]，目标是要极小化X[i] + Y[i]的总和。
我们希望-D <= B[i] - B[i+1] <= D
也就是 -D <= A[i] + X[i] - Y[i] - A[i+1] - X[i+1] + Y[i+1] <= D
也就是 -D - P[i] <= X[i] - Y[i] - X[i+1] + Y[i+1] <= D - P[i]
拆成两个限制式，然后转成标准式
X[i] - Y[i] - X[i+1] + Y[i+1] + S[i] = D - P[i] (1)
X[i] - Y[i] - X[i+1] + Y[i+1] - T[i] = -D - P[i] (2)
从(1)和(2)可知S[i] + T[i] = 2D，所以其实只要
保留其中一个限制式，然后设定S或是T的上限为2D即可。
最后把这n-1个等式加总，然后两边都乘以负一，得到一个新的多余的限制式。
但是结果会是一个min-cost flow的形式，就可以用min-cost flow解了。
在(1)和(2)，我们可以多作一些处理。
当D < P[i]时，(1)的右边 < 0，所以可以设定S[i]的下界为P[i] - D。
当-D > P[i]时，(2)的右边 > 0，所以可以设定T[i]的下界为-P[i] - D。
在这两种case，右手边都可以化简为0。