代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
int a[105][105],f[105][105][5055],mx = -3e9;
signed main(int argc, char **argv){
	int n,k;
	cin >> n >> k;
	for (int i = 1;i <= n;i++){
		for (int j = 0;j <= n;j++){
			for (int l = 0;l <= k;l++){
				f[i][j][l] = -3e9;
			}
		}
	}
	for (int i = 1;i <= n;i++){
		for (int j = 1;j <= i;j++){
			cin >> a[i][j];
			for (int l = 0;l <= k && l <= i;l++){
				f[i][j][l] = max(f[i - 1][j][l],f[i - 1][j - 1][l]) + a[i][j];
				if (l != 0)	f[i][j][l] = max(f[i][j][l],max(f[i - 1][j][l - 1],f[i - 1][j - 1][l - 1]) + a[i][j] * 3);
			}
		}
	}
	k = min(n,k);
	for (int j = 1;j <= n;j++){
		for (int l = 0;l <= k;l++){
			mx = max(mx,f[n][j][l]);
		}
	}
	cout << mx;
	return 0;
}

参考与鸣谢

参考了洛谷的这篇题解

老师代码+我的格式化

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=105;
int dp[N][N][N*N/2],a[N][N];
int n,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));
	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 l=0;l<=min(k,i);l++)
			{
				dp[i][j][l]=max(dp[i-1][j][l],dp[i-1][j-1][l])+a[i][j];
			}
			for(int l=1;l<=min(k,i);l++)
			{
				dp[i][j][l]=max(dp[i][j][l],max(dp[i-1][j][l-1],dp[i-1][j-1][l-1])+a[i][j]*3);
			}	
		}
	}		
	int ans=-1e18;
	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;
}

老师代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 105;
int dp[N][N][N * N / 2], a[N][N];
int n, 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);
	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 l = 0; l <= min(k, i); l++)
				dp[i][j][l] = max(dp[i - 1][j][l], dp[i - 1][j - 1][l]) + a[i][j];
			for (int l = 1; l <= min(k, i); l++)
				dp[i][j][l] = max(dp[i][j][l], max(dp[i - 1][j][l - 1], dp[i - 1][j - 1][l - 1]) + a[i][j] * 3);
		}
	int ans = -1e18;
	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;
}