考虑令 $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 了 …

代码:Submission #131074597 – Codeforces

分类: 文章

Qiuly

QAQ

0 条评论

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

*

code