记录编号	98905	评测结果	AAWAAATWTT
题目名称	积木游戏	最终得分	50
用户昵称	digital-T	是否通过	未通过
代码语言	C++	运行时间	4.002 s
提交时间	2014-04-25 14:42:45	内存使用	2.94 MiB

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
int T,N,M,K;
int f[2][70][70][70];
int brick[70][70],sum[70][70];
int Ans;
int main()
{
	freopen("bricka.in","r",stdin);
	freopen("bricka.out","w",stdout);
	memset(sum,0,sizeof(sum));
	scanf("%d",&T);
	for(int ttt=1;ttt<=T;ttt++)
	{
		printf("Case %d:",ttt);
		scanf("%d%d%d",&N,&M,&K);
		Ans=0;
		K=N*M-K;
		memset(f,0,sizeof(f));
		for(int i=N;i>=1;i--)
			for(int j=1;j<=M;j++)
			{
				scanf("%d",&brick[i][j]);
				sum[i][j]=sum[i][j-1]+brick[i][j];
			}
		for(int i=1;i<=M;i++)
			for(int j=i;j<=M;j++)
			{
				f[0][i][j][j-i+1]=sum[1][j]-sum[1][i-1];
				Ans=max(Ans,f[0][i][j][j-i+1]);
			}
		for(int i=2;i<=N;i++)
		{
			memset(f[(i&1)^1],0,sizeof(f[(i&1)^1]));
			for(int j=1;j<=M;j++)
				for(int k=j;k<=M;k++)
				{
					for(int jj=j;jj<=k;jj++)
						for(int kk=jj;kk<=M;kk++)
							for(int l=k-j+1;l<=K;l++)
								if(f[i&1][jj][kk][l-(k-j+1)]!=0)
								{
									f[(i&1)^1][j][k][l]=max(f[(i&1)^1][j][k][l],f[i&1][jj][kk][l-(k-j+1)]+sum[i][k]-sum[i][j-1]);
									if(l==K)Ans=max(Ans,f[(i&1)^1][j][k][l]);
								}
					for(int kk=j;kk<=k;kk++)
						for(int jj=1;jj<=kk;jj++)
							for(int l=k-j+1;l<=K;l++)
								if(f[i&1][jj][kk][l-(k-j+1)]!=0)
								{
									f[(i&1)^1][j][k][l]=max(f[(i&1)^1][j][k][l],f[i&1][jj][kk][l-(k-j+1)]+sum[i][k]-sum[i][j-1]);
									if(l==K)Ans=max(Ans,f[(i&1)^1][j][k][l]);
								}
					for(int jj=1;jj<=j;jj++)
						for(int kk=k;kk<=M;kk++)
							for(int l=k-j+1;l<=K;l++)
								if(f[i&1][jj][kk][l-(k-j+1)]!=0)
								{
									f[(i&1)^1][j][k][l]=max(f[(i&1)^1][j][k][l],f[i&1][jj][kk][l-(k-j+1)]+sum[i][k]-sum[i][j-1]);
									if(l==K)Ans=max(Ans,f[(i&1)^1][j][k][l]);
								}
				}
		}
		printf("%d\n",Ans);
	}
	return 0;
}