洛谷 P2258 子矩阵

洛谷 P2258 子矩阵

Description

• 给出如下定义：

  子矩阵：从一个矩阵当中选取某些行和某些列交叉位置所组成的新矩阵（保持行与列的相对顺序）被称为原矩阵的一个子矩阵。
  例如，下面左图中选取第2、4行和第2、4、5列交叉位置的元素得到一个2*3的子矩阵如右图所示。

  9 3 3 3 9

  9 4 8 7 4

  1 7 4 6 6

  6 8 5 6 9

  7 4 5 6 1

  的其中一个2*3的子矩阵是

  4 7 4

  8 6 9

  相邻的元素：矩阵中的某个元素与其上下左右四个元素（如果存在的话）是相邻的。

  矩阵的分值：矩阵中每一对相邻元素之差的绝对值之和。
  本题任务：给定一个n行m列的正整数矩阵，请你从这个矩阵中选出一个r行c列的子矩阵，使得这个子矩阵的分值最小，并输出这个分值。

Input

• 第一行包含用空格隔开的四个整数n，m，r，c，意义如问题描述中所述，每两个整数之间用一个空格隔开。

  接下来的n行，每行包含m个用空格隔开的整数，用来表示问题描述中那个n行m列的矩阵。

Output

• 输出共1行，包含1个整数，表示满足题目描述的子矩阵的最小分值。

Sample Input

Sample Output

题解：

• 搜索 + dp。
• 非常不错的一道题。
• 首先容易想到dp，于是提出dp(i, j, k, l)表示前i行取j行，取k列取l列的最小分值。
• 但是，我试着按照这个思路去写，越写越乱，然后就雾了。
• 那么，观察数据，n、m都很小。那么我们可以先用搜索枚举出选哪几行，然后再用dp处理选哪几列。那么dp数组就变成了dp(i, j)表示在搜索选出来的行条件下，前i列取j列的最小分值。
• 搞定。
• 但是，dp的边界细节很繁琐，要注意。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#define N 25
using namespace std;

int n, m, r, c, ans = 0x7fffffff;
int a[N][N], def1[N][N], dp[N][N];
int b[N], def2[N];
bool vis[N];

void dfs(int dep)
{
    if(dep > r)
    {
        memset(def1, 0, sizeof(def1));
        memset(def2, 0, sizeof(def2));
        for(int i = 2; i <= m; i++)
            for(int j = 1; j < i; j++)
                for(int k = 1; k <= r; k++)
                {
                    def1[i][j] += abs(a[b[k]][i] - a[b[k]][j]);
                    def1[j][i] += abs(a[b[k]][i] - a[b[k]][j]);
                }
        for(int i = 1; i <= m; i++)
            for(int j = 1; j < r; j++)
                def2[i] += abs(a[b[j]][i] - a[b[j + 1]][i]);
        for(int i = 1; i <= m; i++)
            for(int j = 1; j <= min(c, i); j++)
            {
                if(j == 1) dp[i][j] = def2[i];
                else if(j == i) dp[i][j] = dp[i - 1][j - 1] + def2[i] + def1[j - 1][i];
                else
                {
                    dp[i][j] = 2e8;
                    for(int k = j - 1; k < i; k++)
                        dp[i][j] = min(dp[i][j], dp[k][j - 1] + def1[k][i] + def2[i]);
                }
            }
        for(int i = c; i <= m; i++) ans = min(ans, dp[i][c]);
        return;
    }
    for(int i = 1; i <= n; i++)
        if(!vis[i] && i > b[dep - 1])
        {
            vis[i] = 1;
            b[dep] = i;
            dfs(dep + 1);
            vis[i] = 0;
        }
}

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];
    dfs(1);
    cout << ans;
    return 0;
}