#P10222. [2022年NK的NOI模拟]最值问题

    ID: 9339 传统题 1000ms 256MiB 尝试: 8 已通过: 2 难度: 8 上传者: 标签>CF2500树形DP单调栈动态规划背包DP数据结构

[2022年NK的NOI模拟]最值问题

每场比赛都应该有至少一道求最值的题目。——《鲁迅说的》

给定一个长度为 nn 的序列 a1,a2,⋯ ,ana_1,a_2,\cdots,a_n,以及一个整数 mm,你需要从 aa 中选出一个长度为 mm 的子序列,ab1,ab2,⋯ ,abma_{b_1},a_{b_2},\cdots,a_{b_m}。定义这个子序列的权值为

$$\sum_{i=1}^m (m\cdot a_{b_i})-\sum_{i=1}^m\sum_{j=1}^m f(\min(b_i,b_j),\max(b_i,b_j))$$

其中 f(l,r)f(l,r) 定义为 min⁡(al,al+1,⋯ ,ar)\min(a_l,a_{l+1},\cdots,a_r)。

请你求出所有子序列的权值的最大值。

输入格式

第一行两个整数,表示 nn 和 mm。

接下来一行 nn 个整数 a1∼ana_1 \sim a_n。

输出格式

一行一个整数,表示答案。

样例输入1

11 5
9 3 7 1 8 12 10 20 15 18 5

样例输出1

176

数据范围

对于 20% 的数据,n≤18n\le 18;

对于 40% 的数据,n≤100n\le 100;

对于 60% 的数据,n≤500n\le 500;

对于 100% 的数据,n≤5000,1≤m≤n,1≤ai<231n\le 5000,1\le m\le n,1\le a_i< 2^{31}。