https://ac.nowcoder.com/acm/problem/20242
有一个n*m的矩阵，请你选出其中k个子矩阵，使得这个k个子矩阵分值之和最大。注意：选出的k个子矩阵不能相互重叠

先看 m , m 只有 1 和 2
先考虑简单情况----m=1 即一维最大子矩阵
状态定义:
f[i][l] 表示到第 i 个点 用掉 l 个矩形的最大值.
转移方程:

for(pre: 1~i-1)
   f[i][l]=max(f[i-1][l],f[pre][l-1]+sum[pre~i]); //sum 表示pre到i的元素值的和

再想 m=2 , 由 m=1 拓展
定义状态 : 表示上面一列到了 i 下面一列到了 j 已选择 l 个矩阵的最大值.
m=2有以下几种情况:

  1. 这个点我不做拓展 --

  2. 由第一列扩展一个小的 s*1 面积的

  3. 由第二列扩展一个小的 s*1 面积的

  4. 两列都作扩展 ,来一个 s*2 面积的
    自然转移方程就出来了

    #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 105;
int c[N][N];
int f[N][N][20];
int sum[N][3];
int main()
{
 int n,m,K;
 cin>>n>>m>>K;
 for(int i=1;i<=n;i++)
     for(int j=1;j<=m;j++){
         scanf("%d",&c[i][j]);
         sum[i][j]=sum[i-1][j]+c[i][j];
     }
 for(int i=1;i<=n;i++)
     for(int j=1;j<=n;j++)
         for(int k=1;k<=K;k++){
             f[i][j][k]=max(f[i-1][j][k],f[i][j-1][k]);
             for(int u=0;u<i;u++)
                 f[i][j][k]=max(f[i][j][k],f[u][j][k-1]+sum[i][1]-sum[u][1]);
             for(int u=0;u<j;u++)
                 f[i][j][k]=max(f[i][j][k],f[i][u][k-1]+sum[j][2]-sum[u][2]);
             if(i==j) {
                 for(int u=0;u<i;u++)
                     f[i][j][k]=max(f[i][j][k],f[u][u][k-1]+sum[i][1]+sum[j][2]-sum[u][1]-sum[u][2]);
             }
         }
 printf("%lld",f[n][n][K]);
 return 0;
}