传送门
记忆化搜索
点击查看代码
#include<bits/stdc++.h>
using namespace std;
using LL=long long; // 定义长整型别名
constexpr int N=110; // 定义最大行数LL a[N][N]; // 存储数字金字塔
LL f[N][N][N]; // 记忆化数组，f[i][j][p]表示从(i,j)位置出发，还剩p次使用3倍机会时的最大得分
bool vis[N][N][N]; // 标记数组，记录状态是否已经计算过
int n,k,ans; // n:行数，k:最大3倍次数，ans:最终答案// 深度优先搜索函数
// 参数：i-当前行，j-当前列，p-已使用的3倍次数
LL dfs(int i,int j,int p)
{// 边界条件检查：超出金字塔范围或使用次数超过限制if(i<0||i>n||j<0||j>n||p>k) return 0;// 如果当前状态已经计算过，直接返回结果if(vis[i][j][p]) {return f[i][j][p];}else{// 如果还有使用3倍的机会if(p!=k){// 选择左下方向并使用3倍机会f[i][j][p]=max(f[i][j][p],dfs(i+1,j,p+1)+3*a[i][j]);// 选择右下方向并使用3倍机会f[i][j][p]=max(f[i][j][p],dfs(i+1,j+1,p+1)+3*a[i][j]);}// 不使用3倍机会的情况// 选择左下方向f[i][j][p]=max(f[i][j][p],dfs(i+1,j,p)+a[i][j]);// 选择右下方向f[i][j][p]=max(f[i][j][p],dfs(i+1,j+1,p)+a[i][j]);// 标记当前状态已计算vis[i][j][p]=true;return f[i][j][p];}
}int main()
{// 输入行数和最大3倍次数scanf("%d%d",&n,&k);// 输入数字金字塔for(int i=1;i<=n;i++){for(int j=1;j<=i;j++){cin>>a[i][j]; }}// 初始化记忆化数组为负无穷（因为可能有负数）memset(f,-0x3f,sizeof(f));// 从金字塔顶部(1,1)开始，当前使用0次3倍机会ans=dfs(1,1,0);// 输出最大得分printf("%lld",ans);return 0;
}
动态规划写法
点击查看代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 105;
int n, k;
ll a[N][N], dp[N][N][5505], maxm = -3e9;
signed main()
{//输入 ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);cin >> n >> k;//初始化 for(int i = 1; i <= n; ++ i)for(int j = 0; j <= n; ++ j)for(int l = 0; l <= k; ++ l)dp[i][j][l] = -3e9; //a[i][j]最小是-1e9，还要乘3，所以设为-3e9(记得开long long）。 //边输入边做dp 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){if(l == 0)dp[i][j][l] = max(dp[i - 1][j][l], dp[i - 1][j - 1][l]) + a[i][j];else{dp[i][j][l] = max(dp[i - 1][j][l], dp[i - 1][j - 1][l]) + a[i][j];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);}}}k = min(k, n); // 不然可能导致没搜到k次，值为-3e9的情况。//搜索答案 for(int j = 1; j <= n; ++ j)for(int l = 0; l <= k; ++ l)maxm = max(maxm, dp[n][j][l]);//输出 cout << maxm;return 0;
}