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\) 。
-
输出格式
输出仅一行,为最大值。
-
样例输入
1 2 |
5 6 16 4 2 2 4 7 |
-
样例输出
1 |
30 |
-
样例说明
对应的 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们的解释
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
#include <cstdio> #include <cstdlib> #include <cstring> #include <climits> #define _max(_a,_b) ((_a)>(_b)?(_a):(_b)) typedef long long LLONG; int a[3050]; LLONG f[1050][8050]; int main() { register int N,M,K;scanf("%d%d%d",&N,&M,&K); for(register int i=1;i<=N;i++) scanf("%d",&a[i]); for(register int i=0;i<=M;i++) for(register int j=0;j<=K;j++) f[i][j]=LLONG_MIN; f[0][0]=0; for(register int i=1;i<=M;i++) for(register int j=1;j<=K;j++) for(register int k=1;k<=N && j-k>=0 && k*i<=j;k++) f[i][j]=_max(f[i][j],f[i-1][j-k]+a[k]); LLONG ans=0; for(register int i=1;i<=K;i++) ans=_max(ans,f[M][i]); printf("%lld\n",ans); return 0; } |
燃鹅我比较菜,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\) !
这样时间复杂度(我不会证),也可以通过本题。
代码(跑得巨慢):
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
#include <cstdio> #include <climits> #define _max(_a,_b) ((_a)>(_b)?(_a):(_b)) typedef long long LLONG; int N,M,K; int a[3050]; LLONG saved[1050][8050]; LLONG DFS(int step,int left,int prev) { if(left<0)return LLONG_MIN; if(step>M)return (left>=0 ? 0 : LLONG_MIN); if(saved[step][left])return saved[step][left]; LLONG ans=LLONG_MIN; for(register int i=1;i<=prev;i++) ans=_max(ans,DFS(step+1,left-i,i)+a[i]); return saved[step][left]=(ans<0?LLONG_MIN:ans); } int main() { scanf("%d%d%d",&N,&M,&K); for(register int i=1;i<=N;i++)scanf("%d",&a[i]); printf("%lld\n",DFS(1,K,N)); return 0; } |