记录编号	462349	评测结果	AAAAAAAAAA
题目名称	[HNOI 2004] 打砖块	最终得分	100
用户昵称	Emine	是否通过	通过
代码语言	C++	运行时间	0.089 s
提交时间	2017-10-21 20:15:56	内存使用	6.68 MiB

//f[i][j][k]表示截止到第i行，总共已经选j个砖块，其中第i行已经选了前k个砖块的最大值。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define maxn 55
using namespace std;
void Emine(){
	freopen("brike.in","r",stdin);
	freopen("brike.out","w",stdout);
}
int n,m,v[maxn][maxn],s[maxn],sum[maxn][maxn],ans,f[maxn][10*maxn][maxn];
int main(){
	Emine();
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)for(int j=i;j<=n;j++) scanf("%d",&v[j][i]);
	for(int i=1;i<=n;i++)for(int j=1;j<=i;j++) sum[i][j]=sum[i][j-1]+v[i][j];
	for(int i=1;i<=n;i++) s[i]=s[i-1]+i;
	memset(f,-333,sizeof(f)); f[0][0][0]=0;
	for(int i=1;i<=n;i++){//截止到第i行
        for(int j=0;j<=min(m,s[i]);j++){//总共已经选j个砖块
            for(int k=0;k<=min(i,j);k++){//第i行已经选了前k个砖块
                for(int p=max(k-1,0);p<i&&s[p]<=j-k;p++)
                    f[i][j][k]=max(f[i][j][k],f[i-1][j-k][p]+sum[i][k]);
                ans=max(ans,f[i][j][k]);
            }
        }
    }
    printf("%d\n",ans);
    return 0; 
}