题目描述
这里有一个n*m的矩阵，请你选出其中k个子矩阵，使得这个k个子矩阵分值之和最大。注意：选出的k个子矩阵不能相互重叠。
输入输出格式
输入格式：
第一行为n,m,k（1≤n≤100,1≤m≤2,1≤k≤10），接下来n行描述矩阵每行中的每个元素的分值(每个元素的分值的绝对值不超过32767)。
输出格式：
只有一行为k个子矩阵分值之和最大为多少。
输入输出样例
3 2 2
1 -3
2 3
-2 3
9
分m=1和m=2两种情况考虑。
m=1时，预处理出前缀和sum[]。
设f[i][j]为到达第i格，已经放了j个子矩阵的最大和，
那么每次先把f[i][j]的值设为f[i-1][j]（第i个元素不属于第j个子矩阵）
剩下的情况就是第i个元素属于第j个子矩阵了。
这时候用max(f[p-1][j-1]+(sum[i]-sum[p-1]), 1<=p<=i)更新f[i][j]的最大值，即枚举第j个子矩阵的起始点。
最终答案为f[n][k]。（边界条件为f[0][j]=0，包含空矩阵）
m=2时，预处理出分别列的前缀和sum1[],sum2[]。
设f[i][j][l]为在第1列到达第i格，第2列到达第j格，已经放了l个子矩阵的最大和，
那么每次先把f[i][j][l]的值设为max(f[i-1][j][l],f[i][j-1][l])（第i行第1列不属于子矩阵或第j行第2列不属于子矩阵，两者取较大值）
剩下的情况就是第i行第1列和第j行第2列都属于子矩阵了。
分两种情况：
一、第i行第1列和第j行第2列属于不同的子矩阵
分别枚举第i行第1列所在子矩阵的起始点和第j行第2列所在子矩阵的起始点并更新答案，
即用max(f[p-1][j][l-1]+(sum1[i]-sum1[p-1]), 1<=p<=i)和max(f[i][p-1][l-1]+(sum2[j]-sum2[p-1]),1<=p<=j)更新f[i][j]的最大值。
二、第i行第1列和第j行第2列属于同一子矩阵
仅当i==j时才包含这种情况（因为i和j要作为当前状态中子矩阵的末尾）。这时候这个子矩阵的列数必定为2。
还是一样枚举子矩阵的起始点，
在i==j的条件下用max(f[p-1][p-1][l-1]+(sum1[i]-sum1[p-1])+(sum2[j]-sum2[p-1]),1<=p<=i)更新答案。
最后答案为f[n][n][k]（边界条件为f[0][0][l]=0，包含空矩阵）
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
int f1[][],f2[][][],a[][],sum1[],sum2[];
int n,m,k;
int main()
{int i,j,l,p;
cin>>n>>m>>k;
for (i=;i<=n;i++)
{
for (j=;j<=m;j++)
{
scanf("%d",&a[i][j]);
if (j==) sum1[i]=sum1[i-]+a[i][j];
else sum2[i]=sum2[i-]+a[i][j];
}
}
if (m==)
{
for (i=;i<=n;i++)
for (j=;j<=k;j++)
{f1[i][j]=f1[i-][j];
for (l=;l<=i;l++)
f1[i][j]=max(f1[i][j],f1[l-][j-]+sum1[i]-sum1[l-]);
}
cout<<f1[n][k];
}
else
{
for (i=;i<=n;i++)
{
for (j=;j<=n;j++)
{
for (l=;l<=k;l++)
{f2[i][j][l]=max(f2[i-][j][l],f2[i][j-][l]);
for (p=;p<=i;p++)
f2[i][j][l]=max(f2[i][j][l],f2[p-][j][l-]+sum1[i]-sum1[p-]);
for (p=;p<=j;p++)
f2[i][j][l]=max(f2[i][j][l],f2[i][p-][l-]+sum2[j]-sum2[p-]);
if (i==j)
for (p=;p<=i;p++)
f2[i][j][l]=max(f2[i][j][l],f2[p-][p-][l-]+sum2[j]-sum2[p-]+sum1[i]-sum1[p-]);
}
}
}
cout<<f2[n][n][k];
}
}