数字三角形的变形。
直接在原来的基础上加个判断 \(3\) 倍的就行了。
参考代码：
点击查看代码
#include<bits/stdc++.h>
using namespace std;
long long n,m,ans=-1e18,a[110][110],dp[110][110][5010];
#define lc(x) x<<1
#define rc(x) x<<1|1
#define lowbit(x) x&-x
#define pb push_back
#define pf push_front
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define endl '\n'
#define QwQ return 0;
int main()
{
IOS;
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=0;j<=n;j++)
for(int k=0;k<=m;k++)
dp[i][j][k]=-1e18;
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)
cin>>a[i][j];
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)
for(int k=0;k<=m && k<=i;k++)
{
if(k==0)
dp[i][j][k]=a[i][j]+max(dp[i-1][j][k],dp[i-1][j-1][k]);
else
{
dp[i][j][k]=a[i][j]+max(dp[i-1][j][k],dp[i-1][j-1][k]);
dp[i][j][k]=max({dp[i][j][k],dp[i-1][j][k-1]+a[i][j]*3,dp[i-1][j-1][k-1]+a[i][j]*3});
}
}
for(int i=1;i<=n;i++)
for(int j=0;j<=min(n,m);j++)
ans=max(ans,dp[n][i][j]);
cout<<ans;
QwQ;
}