信息学奥赛一本通 1968：【14NOIP普及组】子矩阵 | 洛谷 P2258 [NOIP2014 普及组] 子矩阵

【题目链接】

ybt 1968：【14NOIP普及组】子矩阵
洛谷 P2258 [NOIP2014 普及组] 子矩阵

【题目考点】

1. 搜索

2. 动态规划：线性规划

【解题思路】

该问题在二维矩阵中中取子矩阵，可以类比在一维数组中取子序列。
思路上，可以先将二维矩阵变为一维数组，然后求一维数组中满足某一条件的子序列。
记原n行m列的二维数组为a。

1. 搜索确定r行

设r行m列数组b保存从数组a中选出的r行数据。
选择方法为搜索，该问题与“在1~n共n个数字中选出r个数字的组合”是同一个问题。
每次从第k行开始搜索，选出l行。
如果从第k行开始到第n行一共只有l行，即n-k+1 == l，那么选择从第k行到第n行的每一行。
否则，从k开始遍历，确定下一个要选择的行，然后从该行开始继续搜索。
将选出的r行数据填入数组b。
搜索到的总情况数为$C_n^r$，因此这一步的复杂度为$O(C_n^r)$
每次填充r行m列的二维数组，复杂度为$O(rm)$

2. 在r行m列的数组b中，选择分值最小的r行c列子矩阵

在确定数组b后，需要准备两个数组：
一维数组pcol，pcol[j]表示数组b中第j列元素上下相邻所产生的分值加和。

例：假设数组b为
1 2 3
4 5 6
7 8 9
那么pcol[1]就是指第1列1 4 7三个数字上下相邻产生的分值，pcol[1] = |1-4|+|4-7|=6
pcol[3]就是指第3列3 6 9三个数字上下相邻产生的分值，pcol[3] = |3-6|+|6-9|=6

生成pcol数组需要遍历b数组，复杂度为$O(rm)$

二维数组prow，prow[i][j]表示数组b中第i列与第j列元素左右相邻产生的分值加和。

例：假设数组b为
1 2 3
4 5 6
7 8 9
那么prow[1][2]就是指第1列1 4 7与第2列2 5 8左右相邻产生的分值加和，prow[1][2] = |1-2|+|4-5|+|7-8|=3。
prow[1][3]就是指第1列1 4 7与第3列3 6 9左右相邻产生的分值加和，prow[1][3] = |1-3|+|4-6|+|7-9|=6

要生成prow数组，第1次遍历m-1列，第2次遍历m-2列，。。。，最后一次遍历1列，对列共遍历$\frac{m(m-1)}{2}$次，每次遍历各行为r行，总体复杂度为$O(m^{2}r)$

接下来，可以把b数组看作长为m的一维数组，用线性动规的方法求该一维数组上面分值最小的子序列。
类比求最长上升子序列的方法，这里仍然将状态设为“以第x列为结尾的。。。”的形式。

• 状态定义：dp[i][j]：以第j列为结尾的，共有i列的子矩阵的最小分值。
• 初始状态：dp[1][j]子矩阵只有第j列，分值为pcol[j]。
• 状态转移方程：
  要找以第j列为结尾的，共有i列的子矩阵：对所有满足$q<j$且$q\ge i-1$的q，选择以第q列为结尾的，共有i-1列的子矩阵，再加上第j列，构成新的子矩阵。
  • 以第q列为结尾的，共有i-1列的子矩阵的分值为dp[i-1][q]
  • 第j列元素上下相邻产生的分值为pcol[j]
  • 第q列与第j列左右相邻产生的分值为prow[q][j]
    所以这个子矩阵的分值为dp[i][j]=dp[i-1][q]+pcol[j]+prow[q][j]。对所有的情况取最小值。

求出dp数组后，求j从c到m，dp[c][j]的最小值。这就是在选择了这r行后，选择c列能够得到的分值最小的子矩阵的分值。
这个递推过程，i从1循环到c，j从i到m，q从i-1到j-1。复杂度大体为$O(m^{2}c)$

每确定r行后，得到一个分值最小的子矩阵的最小分值。把每种确定r行情况下得到的子矩阵的分值进行比较，选择其中分值最小的分值，即为该题的结果。

复杂度分析：

根据上述分析，首先做搜索r行，复杂度为$O(C_n^r)$，而后并列做了：向数组b赋值$O(rm)$，设pcol数组$O(rm)$，设prow数组$O(m^{2}r)$，递推求状态$O(m^{2}c)$，这四者中$O(m^{2}r)$或$O(m^{2}c)$是最大的，由于r与c的范围相同，所以总体复杂度为$O(C_n^r{m}^{2}r)$
已知n最大为16。根据组合数的概念，当r为8时，$C_n^r$最大，最大为$C_{16}^8=12870$，m与r都取最大值16，估算得到结果：$C_n^r{m}^{2}r=12870\ast 16^2\ast 16=52715520\approx 5.27\ast 10^7<10^8$，这个复杂度是可以接受的。

【题解代码】

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define N 20
int n, m, r, c, mi, ans = INF, a[N][N], b[N][N];//a:原数组 b:临时数组 
int prow[N][N];//prow[i][j]：数组b中第i列与第j列元素左右相邻产生的分值加和
int pcol[N];//pcol[j]：数组b中第j列元素上下相邻所产生的分值加和
int selRow[N], si;//选中的行 
int dp[N][N];//dp[i][j]：数组b中以第j列为结尾的，共有i列的子矩阵的最小分值。
//从第k行开始搜索，还剩下l行 
void dfs(int k, int l)
{
    if(l > n-k+1)//剩下的行数不足l行，直接返回 
        return;
    if(l == 0)//如果已经选完 
    {
        for(int i = 1; i <= si; ++i)//把选中的各行数据转移到b数组 
            for(int j = 1; j <= m; ++j)
                b[i][j] = a[selRow[i]][j];
        memset(pcol, 0, sizeof(pcol));
        for(int j = 1; j <= m; ++j)//初始化pcol，看第j列元素上下相邻产生的分值加和 
            for(int i = 1; i <= r-1; ++i)
                pcol[j] += abs(b[i][j] - b[i+1][j]);
        memset(prow, 0, sizeof(prow));
        for(int j1 = 1; j1 < m; ++j1)//初始化prow，看第j1与第j2列元素左右相邻产生的分值加和
            for(int j2 = j1+1; j2 <= m; ++j2)
                for(int i = 1; i <= r; ++i)
                    prow[j1][j2] += abs(b[i][j1] - b[i][j2]);
        memset(dp, 0x3f, sizeof(dp));//线性dp
        for(int j = 1; j <= m; ++j)//设初始状态 
            dp[1][j] = pcol[j]; 
        for(int i = 2; i <= c; ++i)
            for(int j = i; j <= m; ++j) 
                for(int q = i-1; q < j; ++q)
                    dp[i][j] = min(dp[i][j], dp[i-1][q] + pcol[j] + prow[q][j]);
        mi = INF;
        for(int j = c; j <= m; ++j)//求出的mi为这r行中选出c列得到分值最小的子矩阵的分值 
            mi = min(mi, dp[c][j]);
        ans = min(ans, mi);//更新结果 ans为所有情况下的最小值 
        return;
    }
    for(int i = k; i <= n; ++i)
    {
        selRow[++si] = i;//选择第i行 
        dfs(i+1, l-1);//从下一行开始，需要选择的行数减1 
        --si;//状态还原 
    }
}
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, r);
    cout << ans << endl;
    return 0;
}