solution

注意到

考虑时如何做。

表示前i个位置选出了j段的最大价值。转移就是

同样的方法我们可以类比出时的做法。

表示第1列选到了第i个数,第二列选到了第j个数,总共选了k个矩阵的最大价值。

转移就枚举一下最后放的一个矩阵,如果最后一个矩阵放在了第1列,那就从转移过来。如果最后一个矩阵放在了第2列,那就从转移过来。如果,就可以在最后放一个的矩阵,那就从转移过来

code

/*
* @Author: wxyww
* @Date:   2020-06-05 21:24:15
* @Last Modified time: 2020-06-05 21:59:50
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
#include<cmath>
using namespace std;
typedef long long ll;
const int N = 110;
#define int ll
ll read() {
    ll x = 0,f = 1;char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1; c = getchar();
    }
    while(c >= '0' && c <= '9') {
        x = x * 10 + c - '0'; c = getchar();
    }
    return x * f;
}
int a[N][3],f[N][N][11];
signed main() {
    int n = read(),m = read(),K = read();
    memset(a,-0x3f,sizeof(a));
    a[0][1] = a[0][2] = 0;
    for(int i = 1;i <= n;++i) {
        for(int j = 1;j <= m;++j) {
            a[i][j] = a[i - 1][j] + read();
        }
    }

    memset(f,-0x3f,sizeof(f));
    f[0][0][0] = 0;
    for(int i = 0;i <= n;++i) {
        for(int j = 0;j <= n;++j) {
            for(int k = 0;k <= K;++k) {

                if(i) f[i][j][k] = max(f[i][j][k],f[i - 1][j][k]);

                if(j) f[i][j][k] = max(f[i][j][k],f[i][j - 1][k]);
                if(!k) continue;
                for(int t = 0;t < j;++t)
                    f[i][j][k] = max(f[i][j][k],f[i][t][k - 1] + a[j][2] - a[t][2]);

                for(int t = 0;t < i;++t)
                    f[i][j][k] = max(f[i][j][k],f[t][j][k - 1] + a[i][1] - a[t][1]);

                if(i != j) continue;
                for(int t = 0;t < i;++t)
                    f[i][j][k] = max(f[i][j][k],f[t][t][k - 1] + a[i][1] - a[t][1] + a[i][2] - a[t][2]);
            }
        }
    }

    cout<<f[n][n][K]<<endl;
    return 0;
}