题目描述

从一个矩阵当中选取某些行和某些列交叉位置所组成的新矩阵（保持行与列的相对顺序）,求矩阵中每一对相邻元素之差的绝对值之和。

提供几种思路吧，顺着最常用的思路先写一份DFS减枝，分别枚举选择的行和列，卡常严重所以反反复复减枝超级复杂。 因为不是题目正解所以不多加以注释解释了。

#include <bits/stdc++.h>
using namespace std;
int a[20][20];
int yclb[20][20][20], yclc[20][20][20], ycld[20][20];
int ycla[20], cnt = 2e9; // 前缀和数组
int n, m, r, c;
void dfsr(int x, int e, int ans, int last);
void dfsl(int x, int e, int last)
{
    if (x == r)
    {
        dfsr(0, 0, 0, 0);
        return;
    }
    for (int i = e + 1; i <= x + n - r + 1; i++)
    {
        int lj = 0;
        if (x)
        {
            for (int j = 1; j <= m; j++)
            {
                ycla[j] += yclb[j][last][i];
            }
        }
        for (int j = 1; j <= m; j++)
            for (int k = j + 1; k <= m; k++)
            {
                ycld[j][k] += yclc[i][j][k];
            }
        dfsl(x + 1, i, i);
        if (x)
        {
            for (int j = 1; j <= m; j++)
            {
                ycla[j] -= yclb[j][last][i];
            }
        }
        for (int j = 1; j <= m; j++)
            for (int k = j + 1; k <= m; k++)
            {
                ycld[j][k] -= yclc[i][j][k];
            }
    }
}
void dfsr(int x, int e, int ans, int last)
// x当前选了几列 y=c e用于减枝某列 ans记录上一次的答案 last记录上一列
{
    if (x == c)
    {
        cnt = min(ans, cnt);
        return;
    }
    if (ans > cnt)
        return;
    for (int i = e + 1; i <= m; i++)
    {
        int ans2 = ans + ycla[i] + ycld[last][i];
        if (ans2 < cnt)
            dfsr(x + 1, i, ans2, i);
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m >> r >> c;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            cin >> a[i][j];
        }
        //预处理下面的数组
    for (int i = 1; i <= m; i++)             // 列
        for (int j = 1; j <= n; j++)         // 行
            for (int k = j + 1; k <= n; k++) // 行
            {
                yclb[i][j][k] = abs(a[j][i] - a[k][i]);
            }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            for (int k = j; k <= m; k++)
            {
                yclc[i][j][k] = abs(a[i][j] - a[i][k]);
            }
    dfsl(0, 0, 0);
    cout << cnt;
    return 0;
}

。。调得我头昏，，，卡常严重，改用DP试试。 因为这题涉及两个位置状态量，如果我们用二维的做法进行DP比较困难。 那我们还是沿用上方的部分思路，可以枚举行，将一个二维的问题转化为一个一维DP，优化时间复杂度。

步骤：

先枚举行(DFS或上面的二进制枚举），让所选择的行变为已知量。

计算每列中上下行之间差的绝对值之和 ①

计算每行中任意列与列之间差的绝对值之和 ②

则我们的相邻元素的值为 ①＋②

知道以上条件后之后，我们的问题就变为: 如何在m列中任选c列，使其相邻元素的值最小?

以下是dp部分代码：

    dp[0][0] = 0;
    for (int i = 1; i <= c; i++)
    {
        for (int j = i; j <= m; j++)
        {
            for (int k = 0; k < j; k++)
            {
                dp[i][j] = min(dp[i][j], dp[i - 1][k] + rows[j] + column[k][j]);
            }
            if (i == c)
                ans = min(ans, dp[i][j]);
        }
    }

如果上面还不会做的话提供完整代码（我这里用的二进制枚举+dp）

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e5 + 10;

ll a[20][20], dp[20][20], rows[20], column[20][20];

//分别是 a:输入矩阵的数组  dp：用于进行动态转移  

//rows:存储每一列所有枚举的相邻行的数值

//column:表示从j列到k列的 相邻数之的差（累加所有枚举的行）

int n, m, r, c;

ll ans = 0x3f3f3f3f;//答案

vector<int> line;//存放当前选择的行号

  

void DP(int row)

{

    memset(dp, 127, sizeof(dp));       // 清零

    memset(rows, 0, sizeof(rows));     // 清零

    memset(column, 0, sizeof(column)); // 清零

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

    {

        if (row & (1 << i))

            line.push_back(i + 1);

    }

    for (int i = 1; i <= m; i++) // 列

        for (int j = 1; j < line.size(); j++)

            rows[i] += abs(a[line[j - 1]][i] - a[line[j]][i]); // 计算每列 行与行之间的值的和 设为 A

    for (int i = 0; i < line.size(); i++) // 行

    {

        for (int j = 1; j <= m; j++)         // 列

            for (int k = j + 1; k <= m; k++) // 列

            {

                column[j][k] += abs(a[line[i]][j] - a[line[i]][k]); // 计算每行 列到列的累加 设为 B

            }

    }

    dp[0][0] = 0;                // dp 数组状态 初始化 必须为0

    for (int i = 1; i <= c; i++) // 当前选取的状态

    {

        for (int j = i; j <= m; j++) // 当前枚举的列

        {

            for (int k = 0; k < j; k++) // 上一次选取的列

            {                           // 动态转移方程

                dp[i][j] = min(dp[i][j], dp[i - 1][k] + rows[j] + column[k][j]);

            }

            if (i == c)

                ans = min(ans, dp[i][j]);

        }

    }

    line.clear(); // 如果用vector 一定要记得复原

}

int main()

{

    cin >> n >> m >> r >> c;

    for (int i = 1; i <= n; i++)

        for (int j = 1; j <= m; j++)

        {

            cin >> a[i][j];

        }

    for (int i = 1; i < (1 << n); i++)

    //先二进制枚举行 将二维问题转换为一维问题再动态规划

    {

        if (__builtin_popcount(i) != r)//满足当前选择的数

            continue;

        DP(i);

    }

    cout << ans;

    return 0;

}