现在已经能自然的想到分类讨论了。
注意到m=1或者2，当m=1时，是普通的最大连续字段和，只不过是k个：
设f[i][j]表示前i个数中取出j个矩形的最大和
转移：
选：f[i][j]=max{f[i1][j-1]+s[i]-s[i1-1]}
不选：f[i][j]=max(f[i][j],f[i-1][j])
复杂度O(n^2K)
当m=2时，设w[i][j][k]表示第一列选到第i个数，第二列选到第j个数时，总共k个子矩形的答案
转移有4种情况
当这一位什么都不做的时候：w[i][j][k]=max(w[i-1][j][k],w[i][j-1][k])
当仅选取第一列的某段区间时：w[i][j][k]=max(w[i1][j][k-1]+sum[i][1]-sum[i1-1][1]) 1<=i1<=i-1
当仅选取第二列的某段区间时：w[i][j][k]=max(w[i][j1][k-1]+sum[j][2]-sum[j1-1][2]) 1<=j1<=j-1
当i==j时，可以选取两列一起的矩形：w[i][j][k]=max(w[i1][i1][k]+sum[i][1]+sum[i][2]-sum[i1-1][1]-sum[i1-1][2])
最后所有情况取max
复杂度O(n^3K)
反思：一开始第二种情况的状态想的非常奇怪，后来看了题解，觉得这种转移非常清晰
写程序要正常。。。如果不正常地写然后再补救会出现奇怪的问题
题解摘自：https://blog.csdn.net/zz_ylolita/java/article/details/50647536

上代码：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
#define MAXN 110
#define INF 32768
int n,m,K,a;
int f[MAXN][15],w[MAXN][MAXN][15],s[MAXN],sum[MAXN][2];
int main()
{
scanf("%d%d%d", &n, &m, &K);
if (m==1)
{
for (int i=1;i<=n;i++)
{
scanf("%d", &a);
s[i]=s[i-1]+a;
}
for (int i=0;i<=n;i++)
for (int j=1;j<=K;j++) f[i][j]=-INF;
for (int i=1;i<=n;i++)
for (int j=1;j<=K;j++)
{
f[i][j]=f[i-1][j];
for (int i1=0;i1<i;i1++)
f[i][j]=max(f[i][j],f[i1][j-1]+s[i]-s[i1]);
}
printf("%d", f[n][K]);
}
else
{
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
{
scanf("%d", &a);
sum[i][j]=sum[i-1][j]+a;
}
for (int i=0;i<=n;i++)
for (int j=0;j<=n;j++)
for (int k=1;k<=K;k++) w[i][j][k]=-INF;
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
for (int k=1;k<=K;k++)
{
w[i][j][k]=max(w[i-1][j][k],w[i][j-1][k]);
for (int i1=0;i1<i;i1++)
w[i][j][k]=max(w[i1][j][k-1]+sum[i][1]-sum[i1][1],w[i][j][k]);
for (int j1=0;j1<j;j1++)
w[i][j][k]=max(w[i][j1][k-1]+sum[j][2]-sum[j1][2],w[i][j][k]);
if (i==j)
{
for (int i1=0;i1<i;i1++)
w[i][i][k]=max(w[i][i][k],w[i1][i1][k-1]+sum[i][1]+sum[i][2]-sum[i1][1]-sum[i1][2]);
}
}
printf("%d", w[n][n][K]);
}
}</cstring></cstdlib></cstdio></iostream>