【BZOJ3675】【APIO2014】序列分割

可以首先得到一个结论:一个序列的划分位置如果确定,那么结果就是确定的,与划分顺序无关

于是很容易想到dp,令\(dp_{i,k}\)表示第\(k\)次划分在\(i\)的后面,那么有

$$dp_{i,k}=max{dp_{j,k-1}+(s_i-s_j)*(s_n-s_i)}$$,其中\(j<i\)。

考虑到\(k\)很小,不妨从小往大递推。

令上一层的dp值为\(p\),那么对于\(i\)而言两个决策\(j<k\),若\(j\)劣于\(k\)当且仅当

$$p_j+(s_i-s_j)(s_n-s_i)<p_k+(s_i-s_k)(s_n-s_i)$$

$$(s_n-s_i)(s_k-s_j)<p_k-p_j$$

$$s_n-s_i<\frac{p_k-p_j}{s_k-s_j}$$

直接斜率优化即可。注意元素可能为\(0\)。

说点什么

您将是第一位评论人!

提醒
wpDiscuz