网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
[HNOI2004]打砖块
成绩 | 0 | 开启时间 | 2013年02月21日 星期四 23:02 |
折扣 | 0.8 | 折扣时间 | 2013年02月28日 星期四 23:02 |
允许迟交 | 是 | 关闭时间 | 2013年02月28日 星期四 23:02 |
输入文件 | brike.in | 输出文件 | brike.out |
【题目描述】
在一个凹槽中放置了n层砖块,最上面的一层有n块砖,第二层有n-1块,……最下面一层仅有一块砖。第i层的砖块从左至右编号为1,2,……i,第i层的第j块砖有一个价值a[i,j](a[i,j]<=50)。下面是一个有5层砖块的例子:
如果你要敲掉第i层的第j块砖的话,若i=1,你可以直接敲掉它,若i>1,则你必须先敲掉第i-1层的第j和第j+1块砖。
你的任务是从一个有n(n<=50)层的砖块堆中,敲掉(m<=500)块砖,使得被敲掉的这些砖块的价值总和最大。
【输入格式】
你将从文件中读入数据,数据的第一行为两个正整数,分别表示n,m,接下来的第i每行有n-i+1个数据,分别表示a[i,1],a[i,2]……a[i,n – i + 1]。
【输出格式】
输出文件中仅有一个正整数,表示被敲掉砖块的最大价值总和。
【样例输入】
4 5 2 2 3 4 8 2 7 2 3 49
【样例输出】
19 (敲掉第一层的四块砖,再敲掉第二层的第一块砖,2+2+3+4+8=19)
【提示】
运行时限:1秒钟
本题目一共有十个测试点,每个测试点的分数为总分数的10%。对于每个测试点来说,如果你给出的答案正确,那么你将得到该测试点全部的分数,否则得0分。