#P5125. [Lydsy1712月赛]小Q的书架

    ID: 2318 传统题 1500ms 256MiB 尝试: 361 已通过: 121 难度: 8 上传者: 标签>难度分类提高+/省选-动态规划线性 DP四边形不等式决策单调性分治优化 DP数据结构树状数组排序与序列处理滑动窗口滚动数组CF2500决策单调性优化DP

[Lydsy1712月赛]小Q的书架

小 Q 的书架

题目描述

小 Q 有 nn 本编号互不相同的书,正零乱地在地上排成一排。他要将这一排书划分成恰好 kk 个非空连续段,然后按现在的顺序将每段放到一层书架上。

放好后,他要将每层的书分别按编号从小到大排序。每次可以在1单位时间内交换同一层的两本相邻的书。

请计算如何划分及交换,能使总交换次数最少。

输入格式

从标准输入读入。

第一行两个正整数 n,kn,k,1≤n≤400001\le n\le40000,1≤k≤min⁡(10,n)1\le k\le\min(10,n)。

第二行 nn 个互不相同的正整数 a1,…,ana_1,\ldots,a_n,1≤ai≤n1\le a_i\le n,表示地面上各本书的编号。

输出格式

向标准输出写出一行一个整数,表示最少的总交换次数。

样例输入

6 3
4 3 6 2 5 1

样例输出

1

样例说明

按 [4,3,6][4,3,6]、[2,5][2,5]、[1][1] 划分,需要交换 1+0+0=11+0+0=1 次。

原题时间限制20秒,空间限制256 MB。

鸣谢Claris提供