#P1437. [HNOI2004] 敲砖块
[HNOI2004] 敲砖块
题目背景
无
题目描述
在一个凹槽中放置了 层砖块、最上面的一层有 块砖,从上到下每层依次减少一块砖。每块砖都有一个分值,敲掉这块砖就能得到相应的分值,如下图所示:
14 15 4 3 23
33 33 76 2
2 13 11
22 23
31
如果你想敲掉第 层的第 块砖的话,若 ,你可以直接敲掉它;若 ,则你必须先敲掉第 层的第 和第 块砖。
你现在可以敲掉最多 块砖,求得分最多能有多少。
输入格式
输入文件的第一行为两个正整数 和 ;接下来 行,描述这 层砖块上的分值 ,满足 。
对于 的数据,满足 ,;
输出格式
输出文件仅一行为一个正整数,表示被敲掉砖块的最大价值总和。
4 5
2 2 3 4
8 2 7
2 3
49
19