题目链接：传送门

Description

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

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

如果你想敲掉第 i 层的第j 块砖的话，若i=1，你可以直接敲掉它；若i>1，则你必须先敲掉第i-1 层的第j 和第j+1 块砖。 你现在可以敲掉最多 m 块砖，求得分最多能有多少。

Input

输入文件的第一行为两个正整数 n 和m；接下来n 行，描述这n 层砖块上的分值

TeX parse error: Undefined control sequence \[

,满足0 ≤ a[i][j] ≤ 100 对于 100%的数据，满足1≤n≤50，1 ≤ m ≤ n * (n+1)/2；

Output

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

Sample Input

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

Sample Output

19

Solution

一道Dp题。如果顺着考虑的话，我们会发现因为第i列的答案和i + 1有关，因此会有后效性 但是如果我们倒着考虑的话就不会有这个问题 设

TeX parse error: Undefined control sequence \[

表示第i列从上往下连续选j个，从i列到第N列总共选了k个的答案， 那么有

TeX parse error: Undefined control sequence \[

max后面的东西用前缀和预处理出即可

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>
using namespace std;
const int Maxn = 1300;
int A[55][55], Dp[55][55][Maxn];
int Sum[55][55];
int N, M;
int main()
{
#ifdef hk_cnyali
    freopen("A.in", "r", stdin);
    freopen("A.out", "w", stdout);
#endif
    scanf("%d%d", &N, &M);
    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= N - i + 1; ++j)
            scanf("%d", &A[i][j]);
    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= N - i + 1; ++j)
            Sum[i][j] = Sum[i - 1][j] + A[i][j];
    Dp[N][1][1] = A[1][N];
    int Ans = 0;
    for (int i = N - 1; i >= 1; --i)
    {
        for (int j = 0; j <= N - i + 1; ++j)
        {
            for (int k = (2 * j - 1); k <= M; ++k)
            {
                for (int x = j - 1; x <= N; ++x)
                    Dp[i][j][k] = max(Dp[i][j][k], Dp[i + 1][x][k - j]);
                Dp[i][j][k] += Sum[j][i];
                Ans = max(Ans, Dp[i][j][k]);
            }
        }
    }
    cout<<Ans<<endl;
    return 0;
}