【每日一题】[SCOI2005]最大子矩阵 (DP)

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;
   }