最大子矩阵DP

题意：就是选出K个ab的子矩阵（a<n,b<m），不能选选过的点，然后问你这个K个子矩阵MAX;
题解：首先这题一定要看范围，M=2，那么矩阵就是最大就是N2，我们是不是可以直接枚举暴力来做。
（我们每一列求一个前缀和，第一列sum1,第二列sum2）

1. 首先.我们讨论M=1，是不是矩阵就是一列，然后我们就是dp求区间最大值，dp[i][j]代表前i行里面选择j个的值，dp[i][j]=max(dp[h-1][j-1]+sum1[i]-sum[h-1]);

2.m==2,我们这时候就要开始讨论了 ，首先开一个f[i][j][k],代表选第一列前i行第二列前j行k个子矩阵最大值，那么我们首先选择第一列处理，那就是f[i]j][h]=max(f[a-1][j][h-1]+sum1[i]-sum1[a-1]),
然后第二列处理，f[i][j][h]=max(f[i][a-1][h-1]+sum2[j]-sum2[a-1]),

最后一种情况就是当两列都选择时候，i==j时，那么就是
f[i][j][h]=max(f[i][j][h],f[a-1][a-1][h-1]+sum1[i]-sum1[a-1]+sum2[i]-sum2[a-1]);

#include <bits/stdc++.h>
#define fio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define debug(x) cout << #x << ": " << x << endl;
#define debug1(x) cout<<"xxx"<<endl;
#define ll long long
#define ull unsigned long long
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#define mse(a,b) memset(a,b,sizeof a);
#define fro for
#define it int
using namespace std;
const int maxx=1e6+100;
const int mod=1e9+7;
int sum1[maxx],sum2[maxx];
int dp[500][500],f[500][500][15];
//ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
//inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
int main()
{
   int n,m,k;
   cin>>n>>m>>k;
   if(m==1)
   {
       for(int i=1;i<=n;i++)
       {
           int x;
           cin>>x;
           sum1[i]=sum1[i-1]+x;
       }
       for(int i=1;i<=n;i++)
       {
           for(int j=1;j<=k;j++){
            dp[i][j]=dp[i-1][j];
            for(int h=1;h<=i;h++)
                dp[i][j]=max(dp[i][j],dp[h-1][j-1]+sum1[i]-sum1[h-1]);}
       }
       cout<<dp[n][k]<<endl;
   }
   else
   {
       for(int i=1;i<=n;i++)
       {
           for(int j=1;j<=m;j++)
           {
               int x;
               cin>>x;
               if(j==1)
                sum1[i]=sum1[i-1]+x;
               else
                sum2[i]=sum2[i-1]+x;
           }
       }
       for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        for(int h=1;h<=k;h++)
       {
           f[i][j][h]=max(f[i-1][j][h],f[i][j-1][h]);
           for(int a=1;a<=i;a++)///处理第一列
            f[i][j][h]=max(f[i][j][h],f[a-1][j][h-1]+sum1[i]-sum1[a-1]);
           for(int a=1;a<=j;a++)///处理第二列
           f[i][j][h]=max(f[i][j][h],f[i][a-1][h-1]+sum2[j]-sum2[a-1]);
           if(i==j)
            for(int a=1;a<=i;a++)
            f[i][j][h]=max(f[i][j][h],f[a-1][a-1][h-1]+sum1[i]-sum1[a-1]+sum2[i]-sum2[a-1]);

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