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

· · 题解

本题解在枚举行的组合，利用动态规划优化列的组合的框架下，尝试给出一种尽量减少重复计算的方案。

首先借助递归以增序枚举行的组合。在此过程中，维护两个变量：

以上两个变量可以在递归枚举的过程中进行增量更新，且可以在递归退回时进行回溯。行的组合方案固定后，列的组合方案便可从列数为 1 开始，根据子矩阵最优必有子矩阵去除最后一列后在可选范围内仍然最优的性质，以子矩阵列数和最后一列在原矩阵中的下标构成的二元组为状态，利用动态规划进行优化，逐步扩展到列数为 c 的最优解。完整代码实现如下：

#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;
}

总的复杂度为 O(\mathrm C_n^r(2 + c)m^2)，主要体现为常数优化，相比对每个行的组合方案独立预处理的复杂度 O(\mathrm C_n^r(r + c)m^2) 可减少约一半的计算量，实测用时 126\ \mathrm{ms} / 166\ \mathrm{ms}（包含大小样例）。此外，注意到转置矩阵并相应交换行、列参数不会改变答案，故如果这一操作可以带来运算次数的显著减少，也可以作为一种独立的优化方案。

参考用时来源：