#1688. foo~
foo~
foo~
题目描述
标题: foo~ - Problem - QOJ.ac
#5035. foo~
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