题目传送门
这题乍一看，是不是有点像数字三角形？
实际上，与正解没有任何的联系（bushi)
考试我还对这个所谓的联系想了半小时
要被气死啦！！！
实际上这题要选择的是若干个三角形重叠而成区域，再一看，又有点像CF354D Transferring Pyramid？
Bingo！
然后就发现，这题我做过？！（记忆力惊人）
可以考虑斜着对三角形的轮廓进行 DP，即设 表示当前考虑到斜着的第\(i\)列，总共选了\(j\)个，当前列选择了从上开始的\(k\)个的最大值，转移时，枚举上一列有几个，不能超过\(k+1\)，再加上这一列前\(k\)个的和即可。
(谢谢学长给我讲题！)
然后就异常简单的写4（\(i,j,k,k1\))层循环就可以了
AC Code：
#include<bits/stdc++.h>
#define code using
#define by namespace
#define n_667 std;
code by n_667;
inline int read()
{int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c-48),c=getchar();return x*f;
}
inline void out(int x)
{if(x<0) putchar('-'),x=-x;if(x<10){putchar(x+48);return ;}out(x/10),putchar(x%10+48);return ;
}
int a[55][55];
int s[55][55];
int dp[55][1300][55];
int n,m;
int i,j,k;
int past;
int main()
{n=read(),m=read();for(i=n;i>=1;--i){for(j=1;j<=i;++j){a[i][j]=read();s[j+n-i][n-i+1]+=s[j+n-i][n-i]+a[i][j];}}past=0;for(i=n;i>=1;--i){for(j=0;j<=m;++j){for(k=0;k<=min(j,i);++k){for(int k1=0;k1<=k+1;++k1){dp[i][j][k]=max(dp[i][j][k],dp[i+1][j-k][k1]);}dp[i][j][k]+=s[i][k];}}}out(max(dp[1][m][1],dp[1][m][0]));return 0;
}
下班！！！