[SCOI2005]最大子矩阵

注意到,考虑分类讨论。
当 时 ，设为前个数取了个子矩阵的最大价值，数组为,则有

当 时，设为在第一列前个数，第二列前个数，共有个子矩阵的价值，则有

CODE

#include <algorithm>
#include <cctype>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstring>
#include <deque>
#include <functional>
#include <list>
#include <map>
#include <iomanip>
#include <iostream>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
#define int long long
#define I inline
#define ri register int
#define For(i , x , y) for(ri i = x ; i <= y ; ++ i)
#define Next(i , x) for(ri i = head[x] ; i ; i = e[i].nxt)
I int read() {
    int s = 0 , w = 1; char ch = getchar();
    while(ch < 48 || ch > 57) {if(ch == '-') w = -1; ch = getchar();}
    while(ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48) , ch = getchar();
    return s * w;
}
const int N = 1e2 + 5;
int n , m , K , s1[N] , s2[N] , dp[N][N] , f[N][N][N];

signed main() {
    freopen("in.cpp" , "r" , stdin);
    freopen("out.cpp" , "w" , stdout);
    n = read() , m = read() , K = read();
    if(m == 1) {

        For(i , 1 , n) {
            int x = read() ; s1[i] = s1[i - 1] + x;
        }
        For(k , 1 , K) 
            For(i , 1 , n) {
                dp[i][k] = dp[i - 1][k] ;
                For(j , 0 , i - 1) dp[i][k] = max(dp[i][k] , dp[j][k - 1] + s1[i] - s1[j]);
            }
        cout << dp[n][K] << endl;
        return 0; 
    }
    For(i , 1 , n) {l
        int x = read() , y = read();
        s1[i] = s1[i - 1] + x , s2[i] = s2[i - 1] + y;
    }
    For(k , 1 , K) 
        For(i , 1 , n)
            For(j , 1 , n ) {
                f[i][j][k] = max(f[i - 1][j][k] , f[i][j - 1][k]);
                For(l , 0 , i - 1) f[i][j][k] = max(f[i][j][k] , f[l][j][k - 1] + s1[i] - s1[l]);
                For(l , 0 , j - 1) f[i][j][k] = max(f[i][j][k] , f[i][l][k - 1] + s2[j] - s2[l]);
                if(i == j ) For(l , 0 , j - 1) f[i][j][k] = max(f[i][j][k] , f[l][l][k - 1] + s1[i] - s1[l] + s2[j] - s2[l]);
            }
    cout << f[n][n][K] << endl;
    return 0;
}