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

Sample Output

HINT

Source

刚开始没看清题，以为矩阵宽度范围很大，吓了我一大跳，完全不知道怎么dp，猛然发现宽度最大为2，分两种情况做就好了

这题是个好题，其实就是最大子序列+传纸条的杂交品，我根据丽洁姐的思路来做，当输入矩阵宽度为1时，解法等价于最大子序列，dp数组开二维的，dp[i,j]=第i个序列，取值区间为[1,j]中的最大连续价值和

矩阵宽度为2时，dp数组开三维的，dp[k][i][j]=第k个矩阵，第一列取值区间为[1,i]，第二列取值区间为[1,j]的最大连续和，每个状态分三次决策:

1、该矩阵宽为1，只取第一列的

2、该矩阵宽为1，只取第二列的

3、该矩阵宽为2，第一列、第二列都取，第一列和第二列的部分起点、终点位置应相同

解法大体上类似于最大子序列，不过要注意决策前的数组初始化，以第一种决策为例，每次决策前dp[i][o1][o2]=max(dp[i][o1][o2],dp[i][o1-1][o2])

不过有一个疑惑我还没弄清楚，就是为什么这样DP可以保证各矩阵间互相不重复，据群里某大神说确实可以，仍待求解。。

#include 
  
   
#define INF 100000000
#define LONG int
#define MAXN 120
#define MAXD 13
LONG n,m,k;
LONG max(LONG a,LONG b)
{
	if(a>b) return a;
	return b;
}
void work1() //矩阵宽度为1时的求解，即将问题转化为序列，DP数组开二维的
{
	LONG i,j,o,dp[MAXD][MAXN]={0},sum[MAXN]={0}; //sum[i]=前i个数的和
	for(i=1;i<=n;i++)
	{
		scanf("%d",&sum[i]);
		sum[i]+=sum[i-1];
	}
	for(i=1;i<=k;i++) //第i个序列
	{
		for(j=0;j<=n;j++) //第i个序列的结尾为j
		{
			dp[i][j]=-INF;
			if(j) dp[i][j]=dp[i][j-1]; 
			//如果第i个序列在j结尾的情况,则初始化为第i个序列在j-1结尾的价值和
			//(即不取第j个元素)
			for(o=0;o