YZOJ P3754 Gab数列

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

这样时间复杂度(我不会证),也可以通过本题。

代码(跑得巨慢):

 

 

 

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注