题解：P2258 [NOIP2014 普及组] 子矩阵

#include <algorithm>
#include <iostream>

using namespace std;

int n, m, r, c;
int M[16][16];
int R[16];  // 保存已选中行的下标

int min_score = 0x3fffffff;
int dp[16][16];   // [i, j] -> 选择 i + 1 列，以 j 为终点的最小分数
int inc[16][16];  // [i, j] -> 在第 i 列后增加第 j 列，因元素左右相邻而增加的分数

// 已知 dp[0] 和 inc，优化列的选择方案
void solve()
{
  // 动态规划，从选择 1 列开始，逐步扩展到选择 c 列时的最优解
  for(int i = 1; i < c; ++i) {    // 从选择 i 列扩展到选择 i + 1 列
    for(int j = i; j < m; ++j) {  // 枚举当前列的选择
      // 因元素上下相邻而增加的分数固定为 dp[0][j]，只需优化左右相邻贡献的分数
      dp[i][j] = dp[i - 1][i - 1] + inc[i - 1][j];
      for(int k = i; k < j; ++k) dp[i][j] = min(dp[i][j], dp[i - 1][k] + inc[k][j]);
      dp[i][j] += dp[0][j];
    }
  }
  int score = *min_element(&dp[c - 1][c - 1], &dp[c - 1][m]);
  min_score = min(min_score, score);
}

// 递归枚举行的组合，将选中的行填入 R 中
// 当前选择子矩阵的第 i 行，在原矩阵中至少为第 rmin 行
void solve(int i, int rmin)
{
  if(i == r) return solve();
  R[i] = rmin;

  // 新增一行，更新 dp[0] 和 inc
  for(int j = 0; i && j < m; ++j) dp[0][j] += abs(M[R[i]][j] - M[R[i - 1]][j]);
  for(int j = 0; j < m - 1; ++j) {
    for(int k = j + 1; k < m; ++k) inc[j][k] += abs(M[R[i]][j] - M[R[i]][k]);
  }

  solve(i + 1, rmin + 1);

  // 回溯
  for(int j = 0; j < m - 1; ++j) {
    for(int k = j + 1; k < m; ++k) inc[j][k] -= abs(M[R[i]][j] - M[R[i]][k]);
  }
  for(int j = 0; i && j < m; ++j) dp[0][j] -= abs(M[R[i]][j] - M[R[i - 1]][j]);

  if(n - (rmin + 1) >= r - i) solve(i, rmin + 1);
}

int main()
{
  cin >> n >> m >> r >> c;
  for(int i = 0; i < n; ++i) {
    for(int j = 0; j < m; ++j) cin >> M[i][j];
  }
  solve(0, 0);
  cout << min_score << endl;
  return 0;
}