初拿到手感觉限制太多了，不好硬做，于是开始观察。
若要取某一个数，我们要取其左上右上两个数，而这两个数又要取上面三个数，所以取一个数的前提条件其实是取这一个三角形。
举例
2 2 3 4 5
8 2 7 12
2 3 6
4 9
3
比如我要取第3行的6，我首先要取7和12，要取7和12，首先要取3，4，5，所以一层层拓展下去形成一个与整个形状相似的三角形。
形式化总结一下，如果我要取 \(i,j\)， 那么我要取以其为顶点的三角形，即 \(i-1,j\) 和 \(i-1,j+1\) \(etc\)。
所以自然想到做一个前缀和，表示这一个三角形的权值和，然后问题转化成了取哪些点能让我们的和最大。
考虑我选点不是无限制的，是 \(m\) 次，所以我设 \(dp_{i,j,k}\) 表示选到第 \(i\) 行第 \(j\) 列，还剩 \(k\) 次的最大和。
当前点所代表的三角形内数的个数是等差数列求和，即 \(\frac{(i+1) \times i}{2}\) 个数，选这个点就要选这些数。
而如果选的另外的点有重复，还要减去这些重复的点和权值，设这些点的数量为 \(num\) ，和为 \(sum\) ，\(i,j\) 的前缀和为 \(a_{i,j}\)
那么有状态转移方程（\(LaTeX\)太麻烦了qaq）：
if(k>(i+1)*i/2-num) dp[i][j][k]=max(dp[i][j][k],dp[i][j][k-(i+1)*i/2+num]+a[i][j]-sum);
这是最直接的办法，然而我们根本不知道哪里重复了。
所以我们尝试对图形进行进一步的抽象总结。
我们看到多个三角形叠起来会形成一些折线，如图。
再把图搞优美一点 还是很丑qaq
7 \4 \5 3/ 2/ 4 5
1 \3 \6/ 7/ 3 4
5 \8/ \7/ 3 1
2 5 7 3
6 9 2
2 3
9
去掉重复则是
7 \4 5 3 2/ 4 5
1 \3 6 7/ 3 4
5 \8/ \7/ 3 1
2 5 7 3
6 9 2
2 3
9
我们发现这其实就转化成了一个用给定数量的线段围出一段波浪形，要使这一段的值最大的问题。那么我们的转移显然跟当前取的坐标、取到了第几个有关，所以我们可以设计三维 \(dp_{i,j,k}\) ，显然每次通过上一次转移只能从上面和左下，上面是没有意义的，只考虑左下。
然后我们考虑那个前缀和现在要转化成什么，当前考虑到第 \(i\) 行第 \(j\) 列，则第 \(j\) 列我打掉了的砖块是 \(1 \sim i-1\) ，所以对行做前缀和 。
则有 \(dp_{i,j,k}=max(dp_{i,j,k},dp_{l,j-1,k-i}+a_{i,j})\) 。
注意：
1.只在第一行统计答案，避免不合法。
2.先枚举列再枚举行，否则会造成左下的转移没有值。
3.初始值为 \(dp_{0,0,0}=0\)，其他设成负无穷，避免不合法转移。
4.各种变量的范围，行可以不取，即可以为0，列不行。
5.l枚举转折点。
#include<bits/stdc++.h>
using namespace std;
int n,m,a[51][51],b[51][51];
long long dp[52][52][1280],maxi;
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",&b[i][j]);
a[i][j]=a[i-1][j]+b[i][j];
}
}
memset(dp,-0x3f,sizeof(dp));
dp[0][0][0]=0;
for(int j=1;j<=n;++j){
for(int i=0;i+j<=n+1;++i){
for(int l=0;l<=i+1;++l){
for(int k=0;k<=m;++k){
if(k>=i) dp[i][j][k]=max(dp[i][j][k],dp[l][j-1][k-i]+a[i][j]);
}
}
}
}
for(int i=1;i<=n;++i) maxi=max(dp[1][i][m],maxi);
printf("%lld",maxi);
return 0;
}
至此问题得以解决，时间复杂度 \(O(n^3m)\)。
其实还可以优化，但是我懒。