记录编号	127124	评测结果	AAAAAAAAAA
题目名称	[HNOI 2004] 打砖块	最终得分	100
用户昵称	Ezio	是否通过	通过
代码语言	C++	运行时间	0.638 s
提交时间	2014-10-14 21:22:01	内存使用	49.18 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <algorithm>
#include <ctime>
#include <queue>
#include <map>
#include <vector>
#define scafn scanf
#define For(st,ed,i) for(int i=st;i<=ed;++i)
#define Fordown(st,ed,i) for(int i=st;i>=ed;--i)
#define start(a,flag) memset(a,flag,sizeof(a));
using namespace std;
typedef long long ll;typedef unsigned int uint;typedef unsigned long long ull;
const int INF=0x7fffffff;const int inf=0xfffffff;
int tu[51][51],s[51][51],b[51][51];
int f[51][501][501];
int main(){
	freopen("brike.in","r",stdin);
	freopen("brike.out","w",stdout);
	int n,m,ans=0,p;
	start(tu,0);start(s,0);start(b,0);
	scanf("%d%d",&n,&m);
	For(1,n,i)For(i,n,j)scanf("%d",&tu[j][i]);
	For(1,n,i)For(1,i,j)s[i][j]=s[i][j-1]+tu[i][j];
	start(f,-1);
	//For(1,n,i){For(1,n,j)cout<<s[i][j]<<" ";cout<<endl;}
	For(0,n,i)f[i][0][0]=0;
	For(1,n,i)f[i][1][1]=tu[i][1];
	For(1,n,i)For(0,i,k)For(0,m,j){
		if(k<=j)For(k-1,i,p)
			if(f[i-1][j-k][p]!=-1){
				f[i][j][k]=max(f[i-1][j-k][p]+s[i][k],f[i][j][k]);
				if(j==m&&f[i][j][k]>ans)ans=f[i][j][k];
			}
	}cout<<ans<<endl;
	return 0;
}