链接：
@[toc]

题目描述

这里有一个n*m的矩阵，请你选出其中k个子矩阵，使得这个k个子矩阵分值之和最大。 注意：选出的k个子矩阵 不能相互重叠。

输入描述:

第一行为n,m,k（1 ≤ n ≤ 100,1 ≤ m ≤ 2,1 ≤ k ≤ 10），
接下来n行描述矩阵每行中的每个元素的分值(每个元素的分值的绝对值不超过32767)。

输出描述:

只有一行为k个子矩阵分值之和最大为多少。

示例1
输入

3 2 2
1 -3
2 3
-2 3

输出

9

题解：
m的范围是12
当m=1时，就相当于一维数组，求最大连续k段和
dp[i][j]表示前i个位置选出j段的最大价值。
转移方程是
for(z: 1i-1)
dp[i][j]=max(dp[i-1][j],dp[z][j-1]+sum[zi])
sum表示zi的元素值的和
当m=2时，
dp[i][j][l]表示第一列的前i个数，第二列的前j个数总共选了k个子矩形的答案
sum[i][1/2]表示第1列或第二列的前缀和
（其实就是 把m=1的情况进行延伸）
当i = = j时，两列就可以拼成一个矩阵
dp[i][j][k] = max(dp[x][x][k] + sum[i][1] - sum[x-1][1] + sum[i][2] - sum[x-1][2])
仅在第一列选一个区间：
dp[i][j][k]=max(dp[x][j][k-1]+sum[i][1]-sum[x-1][1])
仅在第二列选一个区间：
dp[i][j][k]=max(dp[i][x][k-1]+sum[j][2]-sum[x-1][2])
什么都不选:
dp[i][j][k]=max(dp[i-1][j][k],dp[i][j-1][k])
代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 105;
int a[N][N];
int dp[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++){
         cin>>a[i][j];
         sum[i][j]=sum[i-1][j]+a[i][j];
     }
     for(int i=1;i<=n;i++)
         for(int j=1;j<=n;j++)
         for(int k=1;k<=K;k++){
             dp[i][j][k]=max(dp[i-1][j][k],dp[i][j-1][k]);
             for(int x=0;x<i;x++)
                 dp[i][j][k]=max(dp[i][j][k],dp[x][j][k-1]+sum[i][1]-sum[x][1]);
             for(int x=0;x<j;x++)
                 dp[i][j][k]=max(dp[i][j][k],dp[i][x][k-1]+sum[j][2]-sum[x][2]);
             if(i==j) {
                 for(int x=0;x<i;x++)
                     dp[i][j][k]=max(dp[i][j][k],dp[x][x][k-1]+sum[i][1]+sum[j][2]-sum[x][1]-sum[x][2]);
             }
         }
     cout<<dp[n][n][K];
     return 0;
}