压缩空间的利器 - 「滚动数组」

让数组滚起来!

概述

我们知道,在递推求解某一个题目的时候,很可能会遇到一些空间爆炸的问题。

如出题人把空间限制压得极小,或者本身定义的状态就多到爆炸,再或者数据范围又极大,都可能导致MLE的情况发生。

于是,滚动数组,作为一种压缩空间的利器,应运而生。

还是和例题结合着讲吧。

例题

A HPOJ1024 [QBOI2019]Pass the Ball

题目链接

本题是对NOIP2008普及组T3传球游戏的加强版。

显然我们能够得到状态转移方程式:

$dp_{j,i} = dp_{j-1,i-1} + dp_{j-1,i+1}$

其中$dp_{i,j}$表示经过$j$次传到编号为$i$的人的手中的方案数。

但仔细观察完题面,我们发现,数据范围提升了30倍,而空间限制缩到了32MB!

我们仔细观察一下递推式,会发现:

递推式中仅仅用到了$dp_{i,j}$这一维以及$dp_{i-1,j}$这一维!

所以,滚动数组顾名思义。

我们在求解$dp_{i,j}$这一维时,通过$dp_{i-1,j}$这一维来求。

而当我们递推到$dp_{i+1,j}$这一维时,直接用$dp_{i,j}$这一维覆盖掉之前的$dp_{i-1,j}$即可。

因为递推式中仅仅用到了$dp_{i,j}$这一维以及$dp_{i-1,j}$这一维,所以对于答案并没有影响。

核心代码:(推荐使用位运算&运算符)

1
2
3
4
5
6
7
8
9
int dp[2][MAXN];
dp[0][1] = 1;
for(int i=1;i<=m;i++){
dp[i & 1][1] = dp[(i - 1) & 1][2] + dp[(i - 1) & 1][n];
dp[i & 1][n] = dp[(i - 1) & 1][1] + dp[(i - 1) & 1][n - 1];
for(int j=2;j<=n-1;j++){
dp[i & 1][j] = dp[(i - 1) & 1][j - 1] + dp[(i - 1) & 1][j + 1];
}
}

B 最长公共子序列

这是一个经典的线性dp问题,题意就不再概述了。

众所周知(背),最长公共子序列(以下称为LCS)的状态转移方程式为:

$$dp_{i,j} = 0 \;\;(if \;i=0 or j=0)$$

$$dp_{i,j} = dp_{i-1,j-1}+1 \;\;(if \;a_i = b_i)$$

$$dp_{i,j} = max(dp_{i,j-1},dp_{i-1,j})$$

我们考虑滚动数组优化。

代码

1
2
3
4
5
6
7
8
9
10
11
int dp[2][MAXN];
int now = 0;
int a[MAXN],b[MAXN];
for(int i=0;i<=n;i++){
for(int j=0;j<=m;j++){
if(i == 0 || j == 0)dp[(now+1)&1][j] = 0;
else if(a[i-1] == b[i-1])dp[(now+1)&1][j] = dp[now][j-1] + 1;
else dp[(now+1)&1][j] = std::max(dp[(now+1)&1][j-1],dp[now][j]);
}
now = (now + 1) & 1;
}

斐波那契数列

我们知道,斐波那契数列的递推式用到了$f_{i-1}$和$f_{i-2}$两项。

那么滚动的时候对3取一下%即可啦。

1
2
3
4
5
6
7
#define mod(x) x%3
int f[3];
f[0] = 0;
f[1] = 1;
for(int i=2;i<=n;i++){
f[mod(x)] = f[mod(x - 1)] + f[mod(x - 2)];
}

习题

这里留几道习题强化记忆。

  1. NOI2001炮兵阵地
  2. 完全背包滚动数组优化
  3. 正在寻找。。。。。

THE END