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

发表于 | 评论数： | 阅读次数：

让数组滚起来！

概述

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

如出题人把空间限制压得极小，或者本身定义的状态就多到爆炸，再或者数据范围又极大，都可能导致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