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$ ！

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

代码（跑得巨慢）：