1. 题目

传送门=￣ω￣=

2. 题解

MMP

巨大坑点！——

空矩阵也是子矩阵！

也就是说题目可以转换成——

选择至多 k 个子矩阵互不重叠使得所选部分权值之和最大。

正文

貌似还有一些什么 $O(n^2k)$啊之类的题解

好像甚至还有 $O(n^4)$的算法？

不清楚

我用的是记忆化搜索，代码冗长，但是复杂度是 $O(nk)$的

复杂度还是很优秀的吧 QvQ

对于 m=1

首先规定 $a$表示原矩阵，$a[i,j]$表示矩阵第 $i$行第 $j$列的数字（$i$从 $1$开始，$j$从 $0$开始）。

设 $f[i,j,k]$表示当前 Dp 到第 $i$行且第 $i$行的决策为 $k$且已经建立了 $j$个子矩阵。

$k=0$或 $1$，其中 $0$表示不选择第 $i$行的那个数字，$1$表示选择。

$j$只是新建了多少个子矩阵，其中可能有未完成的矩阵（还要往里面添加数字），也有可能有已经完成的矩阵。

现在我们需要分类讨论：

(1) 当前为第 $i$行，且选择这一行

这种情况下，如果不选择下一行，那么 $f[i,j,1]=f[i+1,j,0]+a[i,0]$

如果选择下一行，那我们有两种决策：一是把下一行合并到第 $i$行的矩阵里来，二是把下一行作为一个新的矩阵的开头。

那么 $f[i,j,1]=max(f[i+1,j,1],f[i+1,j+1,1])+a[i,0]$

综上：$f[i,j,1]=max(f[i+1,j,0],f[i+1,j,1],f[i+1,j+1,1])+a[i,0]$

(2) 当前为第 $i$行，且不选择这一行

这种情况下，如果不选择下一行，那么 $f[i,j,0]=f[i+1,j,0]$

如果选择下一行，因为必须新建一个矩阵，所以 $f[i,j,0]=f[i+1,j+1,1]$

综上：$f[i,j,0]=max(f[i+1,j,0],f[i+1,j+1,1])$

这样我们就得到了 $m=1$时的递推式

对于 m=2

我们可以仿照 $m=1$的时候的做法

对于状态的设定依然是（不用仔细看了和 $m=1$的是一样的我复制过来的 QvQ）：

设 $f[i,j,k]$表示当前 Dp 到第 $i$行且第 $i$行的决策为 $k$且已经建立了 $j$个子矩阵。

（注意这下面不一样了=。=）

对于 $k$，我们这样设定：

$k$の取值	所代表意义
0	这一行两个数字都不选
1	选择这一行左边的不选择右边的
2	选择这一行右边的不选择左边的
3	选择这一行的两个数字且合并到一个矩阵内
4	选择这一行的两个数字且分开作为两个矩阵看待

接着，我们依然需要分类讨论。

(1) $k=0$，这一行两个数字都不选

此时下一行的决策有如下几种情况：

• 不选择下一行，$f[i,j,0]=f[i+1,j,0]$
• 选择下一行的左边不选择右边：$f[i,j,0]=f[i+1,j+1,1]$
• 选择下一行的右边不选择左边：$f[i,j,0]=f[i+1,j+1,2]$
• 选择下一行的两个并放到一个矩形内：$f[i,j,0]=f[i+1,j+1,3]$
• 选择下一行的两个并不放到一个矩形内：$f[i,j,0]=f[i+1,j+2,4]$

取 $max$即可

(2) $k=1$，选择这一行左边的不选择右边的

此时下一行的决策有如下几种情况：

• 不选择下一行，$f[i,j,1]=f[i+1,j,0]+a[i,0]$
• 选择下一行的左边不选择右边：$f[i,j,1]=max(f[i+1,j,1],f[i+1,j+1,1])+a[i,0]$（因为可以将下一行合并到当前行作为一个矩阵也可以新建矩阵）
• 选择下一行的右边不选择左边：$f[i,j,1]=f[i+1,j+1,2]+a[i,0]$
• 选择下一行的两个并放到一个矩形内：$f[i,j,1]=f[i+1,j+1,3]+a[i,0]$（因为此时下一行是一个完整的宽度为 2 的矩形，无法合并到当前行）
• 选择下一行的两个并不放到一个矩形内：$f[i,j,1]=max(f[i+1,j+1,4],f[i+1,j+2,4])+a[i,0]$（因为此时下一行会出现两个小的分开的格子，可以将左边的那个合并到当前行，也可以将两个都视作新建的矩阵）

依然是取 $max$

(3) $k=2$，选择这一行右边的不选择左边的

此时下一行的决策有如下几种情况：

• 不选择下一行，$f[i,j,2]=f[i+1,j,0]+a[i,1]$
• 选择下一行的左边不选择右边：$f[i,j,2]=f[i+1,j+1,1]+a[i,1]$
• 选择下一行的右边不选择左边：$f[i,j,2]=max(f[i+1,j,2],f[i+1,j+1,2])+a[i,1]$（因为可以将下一行合并到当前行作为一个矩阵也可以新建矩阵）
• 选择下一行的两个并放到一个矩形内：$f[i,j,2]=f[i+1,j+1,3]+a[i,1]$（因为此时下一行是一个完整的宽度为 2 的矩形，无法合并到当前行）
• 选择下一行的两个并不放到一个矩形内：$f[i,j,2]=max(f[i+1,j+1,4],f[i+1,j+2,4])+a[i,1]$（因为此时下一行会出现两个小的分开的格子，可以将右边的那个合并到当前行，也可以将两个都视作新建的矩阵）

还是取 $max$

(4) $k=3$，选择这一行的两个数字且合并到一个矩阵内

• 不选择下一行，$f[i,j,3]=f[i+1,j,0]+a[i,0]+a[i,1]$
• 选择下一行的左边不选择右边：$f[i,j,3]=f[i+1,j+1,1]+a[i,0]+a[i,1]$
• 选择下一行的右边不选择左边：$f[i,j,3]=f[i+1,j+1,2]+a[i,0]+a[i,1]$
• 选择下一行的两个并放到一个矩形内：$f[i,j,3]=max(f[i+1,j,3],f[i+1,j+1,3])+a[i,0]+a[i,1]$
• 选择下一行的两个并不放到一个矩形内：$f[i,j,3]=f[i+1,j+2,4]+a[i,0]+a[i,1]$（虽然它们都选择一行的两个，但是是不能合并的！）

继续取 $max$

(4) $k=4$，选择这一行的两个数字且分开作为两个矩阵看待

• 不选择下一行，$f[i,j,4]=f[i+1,j,0]+a[i,0]+a[i,1]$
• 选择下一行的左边不选择右边：$f[i,j,4]=max(f[i+1,j,1],f[i+1,j+1,1])+a[i,0]+a[i,1]$
• 选择下一行的右边不选择左边：$f[i,j,4]=max(f[i+1,j,2],f[i+1,j+1,2])+a[i,0]+a[i,1]$
• 选择下一行的两个并放到一个矩形内：$f[i,j,4]=f[i+1,j+1,3]+a[i,0]+a[i,1]$
• 选择下一行的两个并不放到一个矩形内：$f[i,j,4]=max(f[i+1,j,4],f[i+1,j+1,4],f[i+1,j+2,4])+a[i,0]+a[i,1]$（可以选择合并两个矩形、合并其中一个或者一个都不合并）

QvQ 仍然取 $max$

经过艰苦卓绝的分类讨论，我们得到了 $m=2$时的递推式

很显然，复杂度是 $O(nk)$的！

至此，我们就可以写出这题的代码啦！

代码：

#include <bits/stdc++.h>

#define NS (105)
#define KS (15)
#define INF (10000000)
#define MEM (-2122219135)

using namespace std;

template <typename _Tp> inline void IN(_Tp& dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

int n, m, k, arr[NS][2], f[NS][KS][5];

int Dp1(int a, int s, int c)
{
    if (s > k) return -INF;
    if (a > n) return 0;
    int& F = f[a][s][c];
    if (F != MEM) return F;
    if (c == 1)
    {
        F = max(Dp1(a + 1, s, 1), Dp1(a + 1, s + 1, 1));
        F = max(F, Dp1(a + 1, s, 0)) + arr[a][0];
        return F;
    }
        F = max(Dp1(a + 1, s + 1, 1), Dp1(a + 1, s, 0));
        return F;
}

int Dp2(int a, int s, int c)
{
    if (s > k) return -INF;
    if (a > n) return 0;
    int& F = f[a][s][c];
    if (F != MEM) return F;
    if (c == 0)
    {
        F = max(Dp2(a + 1, s, 0), Dp2(a + 1, s + 1, 1));
        F = max(F, Dp2(a + 1, s + 1, 2));
        F = max(F, Dp2(a + 1, s + 1, 3));
        F = max(F, Dp2(a + 1, s + 2, 4));
        return F;
    }
    if (c == 1)
    {
        F = max(Dp2(a + 1, s, 1), Dp2(a + 1, s + 1, 1));
        F = max(F, Dp2(a + 1, s, 0));
        F = max(F, Dp2(a + 1, s + 1, 2));
        F = max(F, Dp2(a + 1, s + 1, 3));
        F = max(F, Dp2(a + 1, s + 1, 4));
        F = max(F, Dp2(a + 1, s + 2, 4)) + arr[a][0];
        return F; 
    }
    if (c == 2)
    {
        F = max(Dp2(a + 1, s, 2), Dp2(a + 1, s + 1, 2));
        F = max(F, Dp2(a + 1, s, 0));
        F = max(F, Dp2(a + 1, s + 1, 1));
        F = max(F, Dp2(a + 1, s + 1, 3));
        F = max(F, Dp2(a + 1, s + 1, 4));
        F = max(F, Dp2(a + 1, s + 2, 4)) + arr[a][1];
        return F; 
    }
    if (c == 3)
    {
        F = max(Dp2(a + 1, s, 3), Dp2(a + 1, s + 1, 3));
        F = max(F, Dp2(a + 1, s, 0));
        F = max(F, Dp2(a + 1, s + 1, 1));
        F = max(F, Dp2(a + 1, s + 1, 2));
        F = max(F, Dp2(a + 1, s + 2, 4)) + arr[a][0] + arr[a][1];
        return F; 
    }
        F = max(Dp2(a + 1, s, 4), Dp2(a + 1, s + 1, 4));
        F = max(F, Dp2(a + 1, s + 2, 4));
        F = max(F, Dp2(a + 1, s, 0));
        F = max(F, Dp2(a + 1, s, 1));
        F = max(F, Dp2(a + 1, s + 1, 1));
        F = max(F, Dp2(a + 1, s, 2));
        F = max(F, Dp2(a + 1, s + 1, 2));
        F = max(F, Dp2(a + 1, s + 1, 3)) + arr[a][0] + arr[a][1];
        return F;
}

int main (int argc, char const* argv[])
{
    IN(n), IN(m), IN(k), memset(f, -127, sizeof(f));
    for (int i = 1; i <= n; i += 1)
        for (int j = 0; j < m; j += 1)
            IN(arr[i][j]);
    if (m == 1) printf("%d\n", max(Dp1(1, 1, 1), Dp1(1, 0, 0)));
    else
    {
        int ans = max(Dp2(1, 0, 0), Dp2(1, 1, 1));
        ans = max(ans, Dp2(1, 2, 1));
        ans = max(ans, Dp2(1, 3, 1));
        ans = max(ans, Dp2(1, 4, 2));
        printf("%d\n", ans);
    }
    return 0;
}