bzoj1084【SCOI2005】最大子矩陣

bzoj1084【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

#include
#include
#include
#include
#include
#include
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i--)
#define ll long long
#define inf 1000000000
using namespace std;
int n,m,k;
int f[105][15],g[105][105][15],s[105][3];
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int main()
{
	n=read();m=read();k=read();
	memset(s,0,sizeof(s));
	F(i,1,n) F(j,1,m) s[i][j]=s[i-1][j]+read();
	if (m==1)
	{
		memset(f,0,sizeof(f));
		F(i,1,n) F(j,1,k)
		{
			f[i][j]=f[i-1][j];
			F(l,0,i-1) f[i][j]=max(f[i][j],f[l][j-1]+s[i][1]-s[l][1]);
		}
		printf("%d\n",f[n][k]);
	}
	else
	{
		memset(g,0,sizeof(g));
		F(i,1,n) F(j,1,n) F(l,1,k)
		{
			g[i][j][l]=max(g[i-1][j][l],g[i][j-1][l]);
			F(h,0,i-1) g[i][j][l]=max(g[i][j][l],g[h][j][l-1]+s[i][1]-s[h][1]);
			F(h,0,j-1) g[i][j][l]=max(g[i][j][l],g[i][h][l-1]+s[j][2]-s[h][2]);
			if (i==j) F(h,0,i-1)
				g[i][j][l]=max(g[i][j][l],g[h][h][l-1]+s[i][1]-s[h][1]+s[j][2]-s[h][2]);
		}
		printf("%d\n",g[n][n][k]);
	}
	return 0;
}