BZOJ1084或洛谷2331 [SCOI2005]最大子矩阵

BZOJ原题链接

洛谷原题链接

注意该题的子矩阵可以是空矩阵，即可以不选，答案的下界为\(0\)。
设\(f[i][j][k]\)表示前\(i\)行选择了\(j\)个子矩阵，选择的方式为\(k\)时的最大分值之和。

1. \(k = 0\)表示该行不选数。
2. \(k = 1\)表示该行只选左边的数。
3. \(k = 2\)表示该行只选右边的数。
4. \(k = 3\)表示该行选两个数，但分别属于两个子矩阵。
5. \(k = 4\)表示该行选两个数，属于一个子矩阵。

设一行中左边的数为\(x\)，右边的数为\(y\)。

• \(k = 0\)时
  直接由上一层转移来：\[f[i][j][0] = \max\{ f[i][j][0], f[i - 1][j][0], f[i - 1][j][1], f[i - 1][j][2], f[i - 1][j][3], f[i - 1][j][4] \}\]

• \(k = 1\)时
  若上层状态为\(1\)或\(3\)，则可以直接接上去，其它的都需要另开一个子矩阵：\[f[i][j][1] = \max\{ f[i][j][1], \max\{ f[i - 1][j - 1][0], f[i - 1][j][1], f[i - 1][j - 1][2], f[i - 1][j][3], f[i - 1][j - 1][4] \} + x\}\]

• \(k = 2\)时
  若上层状态为\(2\)或\(3\)，则可以直接接上去，其它的都需要另开一个子矩阵：\[f[i][j][2] = \max\{ f[i][j][2], \max\{ f[i - 1][j - 1][0], f[i - 1][j - 1][1], f[i - 1][j][2], f[i - 1][j][3], f[i - 1][j - 1][4] \} + y\}\]

• \(k = 3\)时
  若上层状态为\(3\)，则可以直接接上去，若为\(0\)或\(4\)，则需要另开两个子矩阵，其它的都需要另开一个子矩阵：\[f[i][j][3] = \max\{ f[i][j][3], \max\{ f[i - 1][j - 2][0], f[i - 1][j - 1][1], f[i - 1][j - 1][2], f[i - 1][j][3], f[i - 1][j - 2][4] \} + x + y \}\]

• \(k = 4\)时
  若上层状态为\(4\)，则可以直接接上去，其它的都需要另开一个子矩阵：\[f[i][j][4] = \max\{ f[i][j][4], \max\{ f[i - 1][j - 1][1], f[i - 1][j - 1][2], f[i - 1][j - 1][3], f[i - 1][j][4] \} + x + y \}\]

\(f\)直接初始化全为\(0\)，因为可以取空矩阵，即不选数。
最后答案为\(\max\{ f[n][k][0], f[n][k][1], f[n][k][2], f[n][k][3], f[n][k][4] \}\)。
在\(DP\)过程中注意判断边界，部分状态对宽度或是子矩阵个数有要求。
因为没开循环，所以代码及其难看。。

#include<cstdio>
#include<cstring>
using namespace std;
const int N = 110;
int f[N][12][5], a[N][N];
inline int re()
{
    int x = 0;
    char c = getchar();
    bool p = 0;
    for (; c < '0' || c > '9'; c = getchar())
        p |= c == '-';
    for (; c >= '0' && c <= '9'; c = getchar())
        x = x * 10 + c - '0';
    return p ? -x : x;
}
inline int maxn(int x, int y)
{
    return x > y ? x : y;
}
inline void ckmaxn(int &x, int y)
{
    if (x < y)
        x = y;
}
int main()
{
    int i, j, n, m, k;
    n = re();
    m = re();
    k = re();
    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
            a[i][j] = re();
    for (i = 1; i <= n; i++)
        for (j = 1; j <= k; j++)
        {
            ckmaxn(f[i][j][0], maxn(f[i - 1][j][0], f[i - 1][j][1]));
            ckmaxn(f[i][j][1], maxn(f[i - 1][j - 1][0], f[i - 1][j][1]) + a[i][1]);
            if (m > 1)
            {
                ckmaxn(f[i][j][0], maxn(f[i - 1][j][2], f[i - 1][j][4]));
                ckmaxn(f[i][j][1], maxn(f[i - 1][j - 1][2], f[i - 1][j - 1][4]) + a[i][1]);
                ckmaxn(f[i][j][2], maxn(maxn(f[i - 1][j - 1][0], f[i - 1][j - 1][1]), maxn(f[i - 1][j][2], f[i - 1][j - 1][4])) + a[i][2]);
                ckmaxn(f[i][j][4], maxn(maxn(f[i - 1][j - 1][0], f[i - 1][j - 1][1]), maxn(f[i - 1][j - 1][2], f[i - 1][j][4])) + a[i][1] + a[i][2]);
                if (j > 1)
                {
                    ckmaxn(f[i][j][0], f[i - 1][j][3]);
                    ckmaxn(f[i][j][1], f[i - 1][j][3] + a[i][1]);
                    ckmaxn(f[i][j][2], f[i - 1][j][3] + a[i][2]);
                    ckmaxn(f[i][j][3], maxn(maxn(f[i - 1][j - 2][0], maxn(f[i - 1][j - 1][1], maxn(f[i - 1][j - 1][2], f[i - 1][j][3]))), f[i - 1][j - 2][4]) + a[i][1] + a[i][2]);
                    ckmaxn(f[i][j][4], f[i - 1][j - 1][3] + a[i][1] + a[i][2]);
                }
            }
        }
    printf("%d", maxn(maxn(f[n][k][0], f[n][k][1]), maxn(f[n][k][2], maxn(f[n][k][3], f[n][k][4]))));
    return 0;
}

BZOJ1084或洛谷2331 [SCOI2005]最大子矩阵

原文：https://www.cnblogs.com/Iowa-Battleship/p/9848816.html