YZOJ P3754 Gab数列

时间限制：2000MS      内存限制：131072KB

难度： \(4.5\)

• 题目描述

给定数列 \(a_1,a_2,\cdots,a_n\)，定义数列 \(b_1,b_2,\cdots,b_m\) 为 Gab数列 当且仅当它满足：

1，\(\forall 1\le i\le m\) 满足 \(b_i\in\mathbf{N^*}\) 且 \(1\le b_i\le n\)

2，\(\sum_\limits{i=1}^{m}b_i\le k\)

求 \(\sum_\limits{i=1}^{m}a_{b_i}\) 的最大值。

• 输入格式

第一行三个整数 \(n\)，\(m\) 和 \(k\) 。

第二行 \(n\) 个整数 \(a_i\) 。

• 输出格式

输出仅一行，为最大值。

• 样例输入

• 样例输出

• 样例说明

对应的 Gab数列 可以为 \(\{1,5,5,1,1,1\}\) 。

• 数据范围

对于 \(15\%\) 的数据，\(n,m\le 8\)，\(k\le 50\)；

对于 \(40\%\) 的数据，\(n,m,k\le 200\)；

对于另外 \(5\%\) 的数据，满足 \(m=k\)；

对于另外 \(5\%\) 的数据，对于 \(1\le i\le j\le n\)，\(a_i\ge a_j\)；

对于 \(100\%\) 的数据，\(n\le 3000\)，\(k\le 8000\)，\(m\le 1000\)，\(1\le a_i\le 10^9\)，\(m\le k\)。

 

 

 …