DP。
但要分类讨论，对于M=1和M=2的情况分别讨论。
1>M=1
设f[i][j]表示选了i个矩阵，到第j位。N^3转移。(前缀和)
2>M=2
设f[i][j][k]表示选了i个矩阵，第一列到i，第二列到j。
枚举i,j,k后枚举j1和k1表示选一行的情况。
如果j==k则可以从之前的两行一起转移。
code：
/**************************************************************
Problem: 1084
User: yekehe
Language: C++
Result: Accepted
Time:112 ms
Memory:1476 kb
****************************************************************/ #include <cstdio>
#include <algorithm>
using namespace std; int f[][][];
int N,M,K,a[][],sum[][];
int F[][];
int S[]; void work()
{
for(int i=;i<=N;i++){scanf("%d",&S[i]);S[i]+=S[i-];}
for(int i=;i<=K;i++)for(int j=;j<=N;j++)F[i][j]=-1e9;
for(int i=;i<=K;i++)
for(int j=;j<=N;j++){
F[i][j]=F[i][j-];
for(int k=;k<j;k++){
F[i][j]=max(F[i][j],F[i-][k]+S[j]-S[k]);
}
}
printf("%d",F[K][N]);
return ;
} int main()
{
scanf("%d%d%d",&N,&M,&K);
if(M==)return work(),;
for(int i=;i<=N;i++)
for(int j=;j<=M;j++){
scanf("%d",&a[i][j]);
sum[i][j]=sum[i-][j]+a[i][j];
}
for(int i=;i<=K;i++)for(int j=;j<=N;j++)for(int k=;k<=N;k++)f[i][j][k]=-1e9;
for(int i=;i<=K;i++)
for(int j=;j<=N;j++)
for(int k=;k<=N;k++){
f[i][j][k]=max(f[i][j-][k],f[i][j][k-]);
for(int j1=;j1<j;j1++)
f[i][j][k]=max(f[i][j][k],f[i-][j1][k]+sum[j][]-sum[j1][]);
for(int k1=;k1<k;k1++)
f[i][j][k]=max(f[i][j][k],f[i-][j][k1]+sum[k][]-sum[k1][]);
if(j==k)
for(int h=;h<j;h++)
f[i][j][k]=max(f[i][j][k],f[i-][h][h]+sum[j][]-sum[h][]+sum[k][]-sum[h][]);
}
printf("%d",f[K][N][N]);
return ;
}