Description

Input

Output

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 <stdio.h>#define INF 100000000#define LONG int#define MAXN 120#define MAXD 13LONG 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<j;o++)				dp[i][j]=max(dp[i][j],dp[i-1][o]+sum[j]-sum[o]); //决策：dp[i][o]+[o,j]全部价值和		}	}	printf("%d\n",dp[k][n]);}void work2() //矩阵宽度为2时的求解，DP数组开三维的,dp[i][j][k]=前i个矩形，第一条结尾为第j个元素，第二条结尾为第k个元素的{	LONG i,j,o1,o2,dp[MAXD][MAXN][MAXN]={0},sum[4][MAXN]={0},s[MAXN]={0}; 	//sum[i列][j行]=第i列前j行元素和,s[i]=前i行元素的和	for(j=1;j<=n;j++)		for(i=1;i<=2;i++)		{			scanf("%d",&sum[i][j]);			s[j]+=sum[i][j]; //s数组预处理,二重循环结束后s[i]=第i行元素和			sum[i][j]+=sum[i][j-1]; //同work1		}	for(i=1;i<=n;i++)		s[i]+=s[i-1]; //循环结束后s[i]=前i行元素和	for(i=1;i<=k;i++) //第i个矩形		for(o1=0;o1<=n;o1++) //第1列在o1结尾			for(o2=0;o2<=n;o2++) //第2列在o2结尾			{				dp[i][o1][o2]=-INF; //初始化				//三种情况:				//1、该矩阵宽为1，只取第一列的				//2、该矩阵宽为1，只取第二列的				//3、该矩阵宽为2，第一列、第二列都取，第一列和第二列的部分起点、终点位置应相同				if(o1) //case1,同work1				{					dp[i][o1][o2]=max(dp[i][o1][o2],dp[i][o1-1][o2]); //初始化					for(j=0;j<o1;j++)						dp[i][o1][o2]=max(dp[i][o1][o2],dp[i-1][j][o2]+sum[1][o1]-sum[1][j]);				}				if(o2) //case2,同work1				{					dp[i][o1][o2]=max(dp[i][o1][o2],dp[i][o1][o2-1]);					for(j=0;j<o2;j++)						dp[i][o1][o2]=max(dp[i][o1][o2],dp[i-1][o1][j]+sum[2][o2]-sum[2][j]);				}				if(o1==o2) //case3				{					for(j=0;j<o1;j++)						dp[i][o1][o2]=max(dp[i][o1][o2],dp[i-1][j][j]+s[o1]-s[j]);				}			}	printf("%d\n",dp[k][n][n]); //输出}int main(){	LONG i,j;	scanf("%d%d%d\n",&n,&m,&k);	if(m==1) work1();	else work2();	return 0;}