#P1437. [HNOI2004] 敲砖块

    ID: 481 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>动态规划dp2004各省省选湖南前缀和

[HNOI2004] 敲砖块

题目背景

题目描述

在一个凹槽中放置了 nn 层砖块、最上面的一层有 nn 块砖,从上到下每层依次减少一块砖。每块砖都有一个分值,敲掉这块砖就能得到相应的分值,如下图所示:

14 15  4  3  23
 33  33 76  2
   2   13 11
     22 23
       31

如果你想敲掉第 ii 层的第 jj 块砖的话,若 i=1i=1,你可以直接敲掉它;若 i>1i>1,则你必须先敲掉第 i1i-1 层的第 jj 和第 j+1j+1 块砖。

你现在可以敲掉最多 mm 块砖,求得分最多能有多少。

输入格式

输入文件的第一行为两个正整数 nnmm;接下来 nn 行,描述这 nn 层砖块上的分值 ai,ja_{i,j},满足 0ai,j1000\leq a_{i,j}\leq 100

对于 100%100\% 的数据,满足 1n501\leq n\leq 501mn×(n+1)21\leq m\leq \frac{n\times(n+1)}{2}

输出格式

输出文件仅一行为一个正整数,表示被敲掉砖块的最大价值总和。

4 5
2 2 3 4
8 2 7
2 3
49
19