记录编号	447666	评测结果	AAAAAAAAAA
题目名称	[HNOI 2004] 打砖块	最终得分	100
用户昵称	CSU_Turkey	是否通过	通过
代码语言	C++	运行时间	0.151 s
提交时间	2017-09-11 09:40:07	内存使用	7.07 MiB

#include<bits/stdc++.h>//我们对图形变一下型
using namespace std; 
int n,m,a[55][55],f[54][54][605],s[55][55];
int main()
{
	freopen("brike.in","r",stdin);
	freopen("brike.out","w",stdout);
//	freopen("1.txt","r",stdin);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){//读入时稍微转换一下 
		for(int j=i;j<=n;j++){
			scanf("%d",&a[j][i]);
			s[j][i]=s[j][i-1]+a[j][i];
		}
	}
/*	for(int i=1;i<=n;i++){
		for(int j=1;j<=i;j++){
			cout<<a[i][j]<<" ";
		}cout<<endl;
	}*/
	for(int i=0;i<=m;i++){
		for(int j=0;j<n;j++){
			for(int o=0;o<=min(i,j);o++){//这里得取min，最多到第j位，但当前一共才敲了i块，所以对ij取min 
				for(int k=0;k<=o+1;k++){//他可以更新到他下一行o+1之前的所有位置 
					f[j+1][k][i+k]=max(f[j+1][k][i+k],f[j][o][i]+s[j+1][k]);
				}
			}
		}
	}
	int ma=-1;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=i;j++){
			ma=max(ma,f[i][j][m]);
		}
	}
	cout<<ma;
	return 0;
}