洛谷P2258 子矩阵题解状态压缩/枚举/动态规划

作者：zifeiy
标签：状态压缩、枚举、动态规划

题目链接：https://www.luogu.org/problem/P2258

这道题目状态压缩是肯定的，我们需要用二进制来枚举状态。

江湖上有一句话，叫做“暴力出奇迹”，所以我一开始是暴力枚举的。

暴力枚举50分

下面是我暴力枚举（骗分50）的思路（后续动态规划的思想也是建立在此基础之上，所以最好还是了解一下）。

首先用二进制枚举所有选择r行的行的排列，然后用二进制枚举所有选择c列的排列，然后计算选中了这r行c列的结果，与最终答案比较。

时间复杂度为 \(O( 2^n \times 2^m \times n \times m ) = O(2^{40})\) ，会超时，过了50%数据。

实现代码如下：

#include <bits/stdc++.h>

using namespace std;

const int maxn = 22;

int n, m, r, c, a[maxn][maxn], b[maxn][maxn], ans = -1;

// 枚举行和列，但是这样只能过50%数据，另50%数据会TLE

void handle() {

    int tmp = 0;

    for (int i = 0; i < r; i ++) for (int j = 0; j < c; j ++) {

        if (i) tmp += abs(b[i][j] - b[i-1][j]);

        if (j) tmp += abs(b[i][j] - b[i][j-1]);

    }

    if (ans == -1 || ans > tmp) {

        ans = tmp;

    }

}

int main() {

    scanf("%d%d%d%d", &n, &m, &r, &c);

    for (int i = 0; i < n; i ++) for (int j = 0; j < m; j ++) scanf("%d", &a[i][j]);

    for (int s1 = 0; s1 < (1<<n); s1 ++) {

        if (__builtin_popcount(s1) != r) continue;

        for (int s2 = 0; s2 < (1<<m); s2 ++) {

            if (__builtin_popcount(s2) != c) continue;

            int id1 = 0;

            for (int i = 0; i < n; i ++) {

                if (s1 & (1<<i)) {

                    int id2 = 0;

                    for (int j = 0; j < m; j ++) {

                        if (s2 & (1<<j)) {

                            b[id1][id2++] = a[i][j];

                        }

                    }

                    id1 ++;

                }

            }

            handle();

        }

    }

    printf("%d\n", ans);

    return 0;

}

枚举+DP100分

首先还是二进制枚举所有选择了r行的排列，然后对于选中的r行，我们定义状态 \(f[i][j]\) 表示到第\(i\)列（且包含第\(i\)列）并且此时选择了 \(j\) 列的最小值。

则我们只需要遍历每一列 \(i\) ，对于列号 \(i\) ：

\(f[i][0] = 0\) ；
\(f[i][1] = t1\) （这里的 \(t1\) 就是选中的r行中元素在第 \(j\) 列的所有元素两两绝对值之和）；

然后我们再从 \(0\) 到 \(i-1\) 遍历列号 \(j\) ，再从 \(2\) 到 \(\min (c, i+1)\) 遍历 \(k\) ，有状态转移方程：

\(f[i][k] = min(f[i][k], f[j][k-1] + t1 + t2)\) 。（其中 \(t2\) 表示第 \(i\) 列和第 \(j\) 列 r对元素绝对值之差的和）。

这样，时间复杂度降到了 \(O( 2^n \times n^3 ) = O( 2^28 )\) ，这样能够过所有100%数据。

实现代码如下：

#include <bits/stdc++.h>

using namespace std;

const int maxn = 22;

const int INF = (1<<29);

int n, m, r, c, a[maxn][maxn], id[maxn], f[maxn][maxn], ans = -1;

void handle() {

    for (int i = 0; i < m; i ++) for (int j = 2; j <= c; j ++) f[i][j] = INF;

    for (int i = 0; i < m; i ++) {

        int t1 = 0;

        for (int j = 1; j < r; j ++) t1 += abs(a[ id[j-1] ][i] - a[ id[j] ][i]);

        f[i][0] = 0;

        f[i][1] = t1;

        for (int j = 0; j < i; j ++) {

            int t2 = 0;

            for (int k = 0; k < r; k ++) t2 += abs(a[ id[k] ][j] - a[ id[k] ][i]);

            for (int k = 2; k <= i+1 && k <= c; k ++)

                f[i][k] = min(f[i][k], f[j][k-1] + t1 + t2);

        }

    }

    for (int i = c-1; i < m; i ++)

        if (ans == -1 || ans > f[i][c]) ans = f[i][c];

}

int main() {

    scanf("%d%d%d%d", &n, &m, &r, &c);

    for (int i = 0; i < n; i ++) for (int j = 0; j < m; j ++) scanf("%d", &a[i][j]);

    for (int s = 0; s < (1<<n); s ++) {

        if (__builtin_popcount(s) != r) continue;

        int cnt = 0;

        for (int i = 0; i < n; i ++) if (s & (1<<i)) id[cnt++] = i;

        handle();

    }

    printf("%d\n", ans);

    return 0;

}

枚举