记录编号	21941	评测结果	AAAAAAAAAA
题目名称	500.技能树	最终得分	100
用户昵称	郭乾乐	是否通过	通过
代码语言	C++	运行时间	0.191 s
提交时间	2010-11-16 07:31:19	内存使用	6.49 MiB

#include<iostream>
#include<fstream>
using namespace std;
int n,m,a[51][51],s[51][51],f[51][51][501];
bool pan[51][51][501];
int minn(int a,int b)
{
	if(a>b) return b;
	else return a;
    return 0;
}
int maxn(int a,int b)
{
	if(a>b)return a;
	else return b;
	return 0;
}
int dfs(int i,int j,int k)
{
	if(i>n||k<=0) return 0;
	if(pan[i][j][k]) return f[i][j][k];
	pan[i][j][k]=true;
	int t;
	t=minn(j,k);
	for(int r=0;r<=t;r++)
		f[i][j][k]=maxn(f[i][j][k],s[i][r]+dfs(i+1,r+1,k-r));
	return f[i][j][k];
}
int main()
{
	ifstream fin("skill.in");
	ofstream fout("skill.out");
	int i,j;
	fin>>n>>m;
	for(i=1;i<=n;i++)
		for(j=i;j<=n;j++)
			fin>>a[j][i];
	for(i=1;i<=n;i++)
		for(j=1;j<=i;j++)
			s[i][j]=s[i][j-1]+a[i][j];
	fout<<dfs(1,1,m);
	return 0;
}