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\)。

 

 

 

---

 

 

 

想透了这个就是个背包。

记 \(f_{i,j}\) 为已选 \(i\) 个，容量为 \(j\) 的背包的最大价值，则 \(f_{i,j}=max\{f_{i-1,j-k}+a_k\}\) 。

那么这样是 \(O(NMK)\) 会 TLE ，怎么优化？？？

注意到其实 \(k\) 不必枚举 \(1\) ~ \(j\) ，只需 \(1\) ~ \(\frac{j}{i}\) 即可。

玄学理解一下，这里是dalao们的解释

 

 

 

 

---

 

 

燃鹅我比较菜，dalao们高端的方法我还是想得一知半解，于是这是我自己的理解。

其实可以考虑使用记搜的方法来实现这个背包。

搜索的时候计两个状态，表示当前搜索到 \(b\) 数组中的第几个数（\(step\)）和还剩下多少容量可以使用（\(left\)）。初始就是 \(DFS(1,K)\) ，转移就是 \(max\{DFS(step+1, left-i)+a_i\}, i=1 \) ~ \(N\) 。

搜索的时候满足 \(left \geq 0\) 。结束状态就是 \(step>M\) 。 然后再记忆化一下，复杂度就是 \(O(NMK)\) 和裸的背包相同。

考虑对这个搜索进行优化，最常见的就是调整搜索序。先搜大的肯定比先搜小的更快，又因为顺序对答案没有影响，所以从大到小搜索 \(b\) 数组中的元素，也就是满足 \(\forall 1 \leq i \leq j \leq N\) 都有 \(b_i \geq b_j\) 。 具体实现就是再计一个变量 \(prev\) 表示 \(b_{step-1}\) 选的数，那么 \(b_{step}\) 选的数一定不能比它大。

要注意的是，因为这个是完全背包问题，如果不按从小到大的顺序枚举 \(b_{step}\) 选的数的话就会造成有重复的状态。所以枚举的时候不能从 \(prev\) ~ \(1\) ，一定要从 \(1\) ~ \(prev\) ！

这样时间复杂度（我不会证），也可以通过本题。

代码（跑得巨慢）：