题目链接
前言
本题解起初参考的题解是错解，感觉只能提供一个思路，然而底下的转移还得自己重推。虚空调题1h，最终战胜。
思路
感觉常规的 DP 不可做，考虑最后答案的形态。显然的，最后的答案形如：
\ /\ /\ __/\ / \ /\/ \/
（有点丑了，能看懂就行）
不难发现这根线上面的部分会被统计进答案。
因此可以对着这根线进行 DP。
\(dp[i][j][k]\) 表示位置 \((i,j)\) ，使用了 \(k\) 个空间形成的答案。那么有以下转移：
- \(dp[i][j][k] = dp[i+1][j-1][k-i]+sum[i][j]\)
- \(dp[i][j][k]=dp[i-1][j][k-1]+a[i][j]\)
- \(dp[i][j][k]=dp[i][j-1][k-i]+sum[i][j]\)
其中 \(sum[i][j]\) 用来表示当前列的前缀和。
做完了，感谢错的题解，让我写了半天。希望我再也不会遇到这种题解。
Code
这里需要注意，线不一定连续，代码中使用了第 0 行用来辅助转移。
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(0),cout.tie(0)
#define File(s) freopen(s".in","r",stdin);freopen(s".out","w",stdout)
#define LL long long
#define fi first
#define se second
const int N = 52;
int n,m;
LL f[N][N][N*(N+1)/2];
int a[N][N];
LL sum[N][N];
int main()
{IOS;cin >> n >> m;for(int i=1;i<=n;i++){for(int j=1;j<=n-i+1;j++){cin >> a[i][j];sum[i][j] = sum[i-1][j] + a[i][j];}}LL ans = 0;for(int j=1;j<=n+1;j++){for(int i=0;i<=n-j+1;i++){for(int l=i;l<=m;l++)f[i][j][l] = max(f[i+1][j-1][l-i]+sum[i][j],f[i][j-1][l-i]+sum[i][j]);for(int l=i;l<=m;l++){if(i > 0) f[i][j][l] = max(f[i][j][l],f[i-1][j][l-1]+a[i][j]);}}}ans = f[0][n+1][m];cout << ans << "\n";return 0;
}