考虑令 $f_{i,j}$ 表示前 $i$ 个数，$b$ 的最后一个是 $j$ 时最小段数。转移：
$$
f_{i,j}=[j\not=a_i-j]+\min_{1\leq k< a_{i-1}}\left(f_{i-1,k}+[a_i-j\not=k]\right)
$$
注意到后面的转移，如果 $f_{i-1,a_i-j}$ 不是最小值，那么从最小值转移不会更劣。
用 set 维护所有最小值的位置，然后再维护一个最小值的值。注意同时需要考虑所有状态都是最小值的情况，需要额外记 $l,r$ 表示 $[l,r]$ 区间的状态同样也是最小值。
至于下标从 $k$ 变成 $a_i-k$ 可以考虑记录 $A,B$，每个数 $x$ 的实际值为 $A+B\times x$，这样就只需要修改 $A,B$ 了。
记得开 long long，虽然我也不知道为什么要开 long long，但是不开就 wa on 8 了 …
0 条评论