Luogu P3648 [APIO2014]序列分割 题解

Describe

题目链接

你正在玩一个关于长度为 $n$ 的非负整数序列的游戏。这个游戏中你需要把序列分成 $k + 1$ 个非空的块。为了得到 $k + 1$ 块,你需要重复下面的操作 $k$ 次:
选择一个有超过一个元素的块(初始时你只有一块,即整个序列)
选择两个相邻元素把这个块从中间分开,得到两个非空的块。
每次操作后你将获得那两个新产生的块的元素和的乘积的分数。你想要最大化最后的总得分。
对于所有的数据,$2\leq n \leq 100000,1\leq k \leq min\left(n-1,200\right)$。

Solution

考虑$dp$。
设$s_i=\sum_{i=1}^n a_i$,$f_{i,j}$表示前$i$个数,分成$j$块。
由题意可得,$f_{i,j}=max \left( f_{k,j-1}+s_k\times(s_i-s_k) \right)$
显然,这个式子可以滚存。
我们设$f_i=f_{i,j},g_k=f_{k,j-1}$。
上面那个式子就变成了:
$$f_i=max(g_k+s_k\times(s_i-s_k))(0\leq j < k <i )$$
显然,这个式子可以斜率优化。
设$k$比$j$更优。
$$g_k+s_k\times(s_i-s_k) \ge g_j+s_j\times(s_i-s_j)$$
化简一下,可得:
$$\frac{(g_j-{s_j}^2)-(g_k-{s_k}^2)}{s_k-s_j}\leq s_i$$
那么维护一个下凸壳即可。(注意分母可能为$0$)

Code

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇