#1688. foo~

    ID: 1688 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest1038来源:qoj.ac数据:公开样例动态规划

foo~

foo~

题目描述

标题: foo~ - Problem - QOJ.ac

#5035. foo~

Statistics

The problem was used in the following contests:

题目描述

我们定义一个序列的权值为 max(前缀最大值个数,后缀最大值个数)。 给定一个长度为 n 的首尾相接的排列 p,你需要将其分成 k 段非空序列,使得每个数都恰好在一段里,且 k 段序列的权值之和尽可能大。

输入格式

第一行两个正整数 n,k,表示排列长度和划分段数。 第二行输入 n 个正整数,表示排列 p。

输出格式

一行一个整数,表示最大权值和。

输入样例1

6 1
4 1 6 2 5 3

输出样例1

4

样例解释1

切开 1 到 6 的边,变为序列 {6,2,5,3,4,1},该序列的后缀最大值有 {6,5,4,1} 四个数。

输入样例2

6 2
4 1 6 2 5 3

输出样例2

5

样例解释2

切开 1 到 6,2 到 5 的边,分成序列 {6,2} 和 {5,3,4,1},权值分别为 2 和 3,权值之和为 5。

输入样例3

18 3
4 6 1 12 15 14 17 13 9 10 5 18 2 8 16 11 3 7

输出样例3

12

数据范围

对于所有数据,满足 1≤k≤n≤6×105,1≤k≤30,保证输入的是一个 {1,2,⋯,n} 的排列。

子任务编号 n k 特殊性质 分值 1 ≤30 - - 10 2 - k=1 10 3 ≤2000 - 数据随机 20 4 ≤5000 - 20 5 ≤5×104 20 6 - 20

数据随机:输入的排列在 n! 种排列中随机生成。

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

6 1
4 1 6 2 5 3
4

样例 2

6 2
4 1 6 2 5 3
5