#5250. 硝华流焰

硝华流焰

题目描述

Yoimiya 和云浅在放烟花。在第 00 秒时,烟花位于坐标 (0,0)(0,0) 处。一个烟花可能走到的位置和它的材料有关。

具体地,烟花的材料可以用一个 0101 序列 ss 表示,烟花将会在空中燃烧 s|s| 秒。对每个 i=1,2,,si=1,2,\cdots,|s|,设烟花现在的位置为 (x,y)(x,y)

  • si=0s_i=0,则烟花在下一秒可能会飞到 (x,y),(x+1,y),(x+1,y+1)(x,y),(x+1,y),(x+1,y+1) 中的一个点。
  • si=1s_i=1,则烟花在下一秒可能会飞到 (x,y),(x1,y),(x1,y1)(x,y),(x-1,y),(x-1,y-1) 中的一个点。

定义 f(s)f(s) 为材料为 ss 的烟花最终可能会飞到的点的数目。

Yoimiya 现在有一个长为 nn0101 序列 aa,她想用这个序列制造恰好 kk 个烟花。具体地,她需要把这个序列划分为互不相交的 kk 个区间,且每个 aia_i 都至少会被划分到一个区间内;由于燃放烟花会带来污染,这个划分方案的污染度就定义为每一段的 ff 值之和。你需要帮她找到污染度最小的划分方案。

形式化地,你需要找到 kk 个区间 [l1,r1],,[lk,rk][l_1,r_1],\cdots,[l_k,r_k] 满足:

  • l1=1,rk=nl_1=1,r_k= n
  • 1ik,liri\forall 1\le i\le k,l_i\le r_i
  • 1ik1,ri+1=li+1\forall 1\le i\le k-1,r_i+1=l_{i+1}

要求最小化 i=1kf(a[liri])\sum_{i=1}^kf(a[l_i\cdots r_i]),其中 a[pq]a[p\cdots q] 表示序列 (ap,ap+1,,aq)(a_p,a_{p+1},\cdots,a_q)

输入格式

第一行两个正整数 n,kn,k

接下来一行 nn 个数 a1,,ana_1,\cdots,a_n 表示序列 aa,保证 ai{0,1}a_i\in\{0,1\}

输出格式

输出一行一个正整数表示答案。

样例 11 输入

6 3
0 0 1 0 1 1

样例 11 输出

19

样例 11 解释

最优方案是将 aa 划分为 a1=(0,0),a2=(1,0),a3=(1,1)a_1=(0,0),a_2=(1,0),a_3=(1,1),可以验证:

  • f(a1)=f(a3)=6f(a_1)=f(a_3)=6
  • f(a2)=7f(a_2)=7

其中以 a2a_2 为材料的烟花能够到达的点是:

  • (1,1),(1,0),(0,1),(0,0),(0,1),(1,0),(1,1)(-1,-1),(-1,0),(0,-1),(0,0),(0,1),(1,0),(1,1)

a1a_1 为材料的烟花能够到达的点是:(0,0),(1,0),(1,1),(2,0),(2,1),(2,2)(0,0),(1,0),(1,1),(2,0),(2,1),(2,2)

测试点约束

对于 100%100\% 的数据,1kn2×105,ai{0,1}1\le k\le n\le 2\times 10^5,a_i\in\{0,1\}。各子任务的约束如下表所示:

子任务编号 nn kk 特殊性质 依赖子任务 分值
Subtask #1 5\le 5 66
Subtask #2 20\le 20 11 99
Subtask #3 200\le 200 1,21,2 1010
Subtask #4 2000\le 2000 1,2,31,2,3 1717
Subtask #5 105\le 10^5 50\le 50 ai=0a_i=0 77
Subtask #6 1,2,51,2,5 1111
Subtask #7 105\le 10^5 ai=0a_i=0 55 1313
Subtask #8 1,2,3,4,5,6,71,2,3,4,5,6,7 1717
Subtask #9 2×105\le 2\times 10^5 1,2,3,4,5,6,7,81,2,3,4,5,6,7,8 1010