记录编号	194067	评测结果	AAAAAAAAAA
题目名称	[HNOI 2004] 打砖块	最终得分	100
用户昵称	Satoshi	是否通过	通过
代码语言	C++	运行时间	0.207 s
提交时间	2015-10-15 21:26:46	内存使用	10.46 MiB

#include <fstream>
#include <algorithm>
#define N 51
#define M 510
using namespace std;
ifstream in("brike.in");
ofstream out("brike.out");
int a[N][N]={0},b[N][N]={0},sum[N][N]={0};
int f[N][M][N]={0},g[N][M][N]={0};
int n,m,ans=0,INF=(1<<30);
void read()
{
	int i,j,k,l,r,t;
	in>>n>>m;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n-i+1;j++)
		{
			in>>a[i][j];
			b[i+j-1][j]=a[i][j];
		}
	}
	for(i=1;i<=n;i++)
	{
		l=1;r=i;
		while(l<=r)
		{
			t=b[i][l];
			b[i][l]=b[i][r];
			b[i][r]=t;
			l++;
			r--;
		}
	}
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=i;j++)
		{
			sum[i][j]=sum[i][j-1]+b[i][j];
		}
	}
	//for(i=0;i<=n;i++)for(j=0;j<=m;j++)for(k=0;k<=n;k++)f[i][j][k]=INF;
	for(i=0;i<=n;i++)f[i][0][0]=0;
	for(i=1;i<=n;i++)f[i][1][1]=b[i][1];
}
void work()
{
	int i,j,k,l;
	for(i=1;i<=n;i++)
	{
		for(j=0;j<=m;j++)
		{
			for(k=i;k>=0;k--)
			{
				if(k>j)continue;
				//g[i][j][k]=max(g[i][j][k+1],f[i][j][k]);
				//f[i][j][k]=max(f[i][j][k],g[i-1][j-k][k-1]+sum[i][k]);
				for(l=k-1;l<=(i-1)&&l<=(j-k);l++)
				{
					f[i][j][k]=max(f[i][j][k],f[i-1][j-k][l]+sum[i][k]);
				}
			}
        }
		for(j=0;j<=m;j++)
		{
			for(k=i-1;k>=0;k--)
			{
				if(k>j)continue;
				g[i][j][k]=max(g[i][j][k+1],f[i][j][k]);
			}
        }
	}
	for(i=1;i<=n;i++)
	{
		for(k=0;k<=n;k++)
		{
			if(f[i][m][k]>ans)ans=f[i][m][k];
		}
	}
	out<<ans<<endl;
}
int main()
{
	read();
	work();
	return 0;
}