Description
这里有一个n*m的矩阵，请你选出其中k个子矩阵，使得这个k个子矩阵分值之和最大。注意：选出的k个子矩阵
不能相互重叠。
Input
第一行为n,m,k（1≤n≤100,1≤m≤2,1≤k≤10），接下来n行描述矩阵每行中的每个元素的分值(每个元素的
分值的绝对值不超过32767)。
Output
只有一行为k个子矩阵分值之和最大为多少。
Sample Input
3 2 2
1 -3
2 3
-2 3
Sample Output
9
Solution
很明显的一点就是DP，可以发现m很小，而且只有两种情况，所以我们可以分情况讨论。
首先第一个(m=1)的时候，题意就变成了给你一串数让你选k段使它的和最大，我们可以直接(O(nk))DP出来。大体方法就是用(f[i][j][0])表示这一个数空下，(f[i][j][1])表示选这一个数，那么我们得到DP方程为：
(f[i][j][0]=max(f[i-1][j][0],f[i-1][j][1]))
(f[i][j][1]=max(f[i-1][j-1][0],f[i-1][j][1])+t)
之后扫一遍数组求出一个maxans就可以了。
对于(m=2)的时候明显我们依然可以使用上面的方法，当然也可以用前缀和进行递推，不过复杂度不是非常优秀，用上面的方法我们仍然可以做到(O(nk))得出答案。
我们用(f[i][j][0])表示空过这一行，(f[i][j][1])表示只选这一行左边的数，(f[i][j][2])表示只选右边的数，(f[i][j][3])表示把这一行的两个数当成两个竖着的矩形选择，(f[i][j][4])表示把这一行的两个数放到一个矩形里。
不难得出我们的5个Dp方程分别为：
(f[i][j][0]=maxx(f[i-1][j][0],f[i-1][j][1],f[i-1][j][2],f[i-1][j][3],f[i-1][j][4]))
(f[i][j][1]=maxx(f[i-1][j-1][0],f[i-1][j][1],f[i-1][j-1][2],f[i-1][j][3],f[i-1][j-1][4])+t1)
(f[i][j][2]=maxx(f[i-1][j-1][0],f[i-1][j-1][1],f[i-1][j][2],f[i-1][j][3],f[i-1][j-1][4])+t2)
(f[i][j][3]=maxx(f[i-1][j-2][0],f[i-1][j-1][1],f[i-1][j-1][2],f[i-1][j][3],f[i-1][j-2][4])+t1+t2)
(f[i][j][4]=maxx(f[i-1][j-1][0],f[i-1][j-1][1],f[i-1][j-1][2],f[i-1][j-1][3],f[i-1][j][4])+t1+t2)
然后依然是扫一遍数组输出即可。
Code
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <string>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#define re register
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define ms(arr) memset(arr, 0, sizeof(arr))
const int inf = 0x3f3f3f3f;
int n,m,k;
int f[101][11][5],g[101][101],a[101][3],t,t1,t2;
inline int read()
{
int x=0,c=1;
char ch=' ';
while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
while(ch=='-') c*=-1,ch=getchar();
while(ch<='9'&&ch>='0')x=x*10+ch-'0',ch=getchar();
return x*c;
}
inline int maxx(int a1,int a2,int a3,int a4,int a5)
{
return max(max(max(max(a1,a2),a3),a4),a5);
}
int main()
{
n=read();m=read();k=read();
for(re int i=1;i<=n;i++)
for(re int j=1;j<=m;j++)
a[i][j]=read();
if(m==1){
for(re int i=1;i<=n;i++)
for(re int j=1;j<=min(k,i);j++){
t=a[i][1];
f[i][j][1]=max(f[i-1][j][1],f[i-1][j-1][0])+t;
f[i][j][0]=max(f[i-1][j][1],f[i-1][j][0]);
}
int ans=0;
for(re int i=1;i<=k;i++)
ans=max(f[n][i][0],f[n][i][1]);
cout<<ans;
return 0;
}
else {
memset(f,-inf,sizeof(f));
for(re int i=0;i<=n;i++)
for(re int j=0;j<=k;j++)
f[i][j][0]=0;
for(re int i=1;i<=n;i++){
for(re int j=1;j<=k;j++){
t1=a[i][1];t2=a[i][2];
f[i][j][0]=maxx(f[i-1][j][0],f[i-1][j][1],f[i-1][j][2],f[i-1][j][3],f[i-1][j][4]);
f[i][j][1]=maxx(f[i-1][j-1][0],f[i-1][j][1],f[i-1][j-1][2],f[i-1][j][3],f[i-1][j-1][4])+t1;
f[i][j][2]=maxx(f[i-1][j-1][0],f[i-1][j-1][1],f[i-1][j][2],f[i-1][j][3],f[i-1][j-1][4])+t2;
f[i][j][3]=maxx(-inf,-inf,f[i-1][j-1][1],f[i-1][j-1][2],f[i-1][j][3])+t1+t2;
if(j>=2) f[i][j][3]=maxx(-inf,-inf,f[i][j][3],f[i-1][j-2][0]+t1+t2,f[i-1][j-2][4]+t1+t2);
f[i][j][4]=maxx(f[i-1][j-1][0],f[i-1][j-1][1],f[i-1][j-1][2],f[i-1][j-1][3],f[i-1][j][4])+t1+t2;
}
}
}
int ans=0;
for(re int i=1;i<=k;i++)
ans=maxx(f[n][i][0],f[n][i][1],f[n][i][2],f[n][i][3],f[n][i][4]);
cout<<ans;
return 0;
}