思路借鉴[CSP-J 2022] 上升点列，真的很像

参考代码：

#include<iostream>
#include<cstring>
#define int long long //依旧不开long long见祖宗
using namespace std;
int n,k,ans=-0x3f3f3f3f;
int a[105][105],dp[105][105][5055];//dp[i][j][k]:到a[i][j]且还剩k次翻倍机会时的最大得分 
signed main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++)for(int j=1;j<=i;j++) cin>>a[i][j];
	memset(dp,-0x3f,sizeof(dp));//胎教化了,a[i][j]可能是负数
	dp[1][1][0]=a[1][1];//初始化
	dp[1][1][1]=a[1][1]*3;
	for(int i=2;i<=n;i++){
		for(int j=1;j<=i;j++){
			for(int kk=0;kk<=k&&kk<=i;kk++){//说实话不知道为什么次数要放里面，但是[CSP-J 2022] 上升点列我是这么写的
				if(!kk) dp[i][j][kk]=max(dp[i-1][j-1][kk],dp[i-1][j][kk])+a[i][j];//没次数直接推下来 
				else dp[i][j][kk]=max(max(dp[i-1][j-1][kk],dp[i-1][j][kk])+a[i][j],max(dp[i-1][j-1][kk-1],dp[i-1][j][kk-1])+3*a[i][j]);//还有次数考虑翻倍
        //这里体现了数组下标从1开始的好处：边界-1不会re
			}
		}
	}
	for(int i=1;i<=n;i++)for(int j=0;j<=k;j++) ans=max(ans,dp[n][i][j]);//最后一层统计答案 
	cout<<ans;
	return 0;
}

时间复杂度:$O(n^3)$

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

浅浅的集个踩

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;
}