懒得写太多字了，自己看吧，两种解法

浅浅的集个踩

DFS

//函数中的c表示目前已经消耗的三倍机会
#include<bits/stdc++.h>
using namespace std;
long long n,k,d[110][110],df[110][110][110];
long long dfs(int a,int b,int c){
	if(b==0||b>a||c>k)return -0x3f3f3f3f3f3f3f;
	if(df[a][b][c]!=-0x3f3f3f3f3f3f3f){
		return df[a][b][c];
	}
	df[a][b][c]=max(max(dfs(a+1,b,c+1)+d[a][b]*3,dfs(a+1,b+1,c+1)+d[a][b]*3),max(dfs(a+1,b,c)+d[a][b],dfs(a+1,b+1,c)+d[a][b]));
	return df[a][b][c];	
}
int main(){
	cin>>n>>k;
	if(n<=k)k=n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=i;j++){
			cin>>d[i][j];
		}
	}
	for(int i=0;i<=n;i++){
		for(int j=0;j<=n;j++){
			for(int l=0;l<=k;l++){
				df[i][j][l]=-0x3f3f3f3f3f3f3f;
			}
		}
	}
	cout<<max(dfs(1,1,0),dfs(1,1,1));
	return 0;
}

dp

//dp的第三维表示已经花的三倍机会
#include<bits/stdc++.h>
using namespace std;
long long n,k,a[110][110],dp[110][110][110],maxn=-0x3f3f3f3f3f3f3f3f;
int main(){
	cin>>n>>k;
	if(k>=n)k=n;//走n步就到底了，所以大于n的k值可以减小为n
	for(long long i=1;i<=n;i++){
	   	for(long long j=1;j<=i;j++){
	   		cin>>a[i][j];
	   	}
	}
	for(int i=0;i<=n;i++){
		for(int j=0;j<=n;j++){
			for(int l=0;l<=k;l++){
				dp[i][j][l]=-0x3f3f3f3f3f3f3f;
			}
		}
	}
	dp[1][1][1]=a[1][1]*3;
	dp[1][1][0]=a[1][1]; 
	for(long long i=2;i<=n;i++){
	   	for(long long j=1;j<=i;j++){
	   		    dp[i][j][0]=max(dp[i-1][j-1][0]+a[i][j],dp[i-1][j][0]+a[i][j]);
	 	        for(long long l=1;l<=i&&l<=k;l++){
	 	    	dp[i][j][l]=max(max(dp[i-1][j-1][l-1]+a[i][j]*3,dp[i-1][j][l-1]+a[i][j]*3),max(dp[i-1][j-1][l]+a[i][j],dp[i-1][j][l]+a[i][j]));
              //考虑是否需要消耗三倍机会
			}
	   	}
	}
	for(int i=1;i<=n;i++){
		for(int j=0;j<=k;j++){
			maxn=max(dp[n][i][j],maxn);
		}
	}
	cout<<maxn;
	return 0;
}