[BZOJ 1084][SCOI2005]最大子矩陣

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