题意：
给出倒三角排列的砖块，每个砖块有一个分值
如果你想敲掉第$i$层的第$j$块砖的话，若$i=1$，你可以直接敲掉它；若$i>1$，则你必须先敲掉第$i-1$层的第$j$和第$j+1$块砖。
你现在可以敲掉最多$m$块砖，求得分最多能有多少。
数据范围： $1\le n\le 50,1\le m\le \frac{n\times (n+1)}{2}$
题解：
容易想到dp，可以从上一行转移过来，且满足最优子结构性质
但是由于此行的决策与上一行的选择方案有关，即不满足无后效性
一种方案是记录上一行的选择情况（即状压dp），但由于空间过大，过不了内存限制
注意到如果敲掉第$i$列第$j$号砖，意味着一定敲掉了其正上方和右上方围成的一个三角形区域（按输入形式构图）
不妨从右往左dp（按列），这样便解决了按行dp不满足无后效性的问题
用$f[i][j][k]$表示敲掉第$i$列第$j$号砖且总共敲掉$k$块砖后的总分值
在$i+1$列（右列）从$j-1$（右上）到$n-i$（最后）枚举$l$，这些情况都至少满足题意
最后再加上当前列的前缀和（即上方所有砖块的分值）
状态转移方程为$$f[i][j][k]=\max\limits_{l=j-1}^{n-i}\{f[i+1][l][k-j]+sum[j][i]\}$$
代码：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<memory.h>
using namespace std;
const int N=50+5;
int n,m,ans;
int a[N][N],f[N][N][N*N>>1];
int main(){
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]);
memset(f,0x80,sizeof(f));
f[n+1][0][0]=0;
for(int i=n;i;i--)
for(int j=0,sum=0;j<=n-i+1;j++,sum+=a[j][i])
for(int k=j;k<=m;k++)
for(int l=max(0,j-1);l<=n-i;l++)
f[i][j][k]=max(f[i][j][k],f[i+1][l][k-j]+sum);
for(int i=1;i<=n;i++)
for(int j=1;j<=n-i+1;j++)
ans=max(ans,f[i][j][m]);
printf("%d",ans);
return 0;
}
/*
4 5
2 2 3 4
8 2 7
2 3
49
*/