自动搬运

查看原文

来自洛谷，原作者为

	Wind_Smiled 风颜悦。颜悦因风起，风起故颜悦。||向着不同的方向、我们逐渐远去、背对背的你我、难能再见||这个OP的 uid：266896259

搬运于2025-08-24 21:26:17，当前版本为作者最后更新于2023-04-03 22:53:21，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意

给定一个 $n$ 阶的数字金字塔，可以使 $k$ 个数变为原来的三倍。每次移动可以到达左下或右下的点，求路径最大的总值。

分析

显然是一个记忆化搜索。由于在 $k$ 次修改下的值的更改，dp 要用三维。第三维记录修改 $p$ 次。

数据范围：$|a_{i,j}| \le 10^{9}$。对于乘三的操作结束之后累加必定会爆 int，所以要开 long long。共有 $n$ 层，故最多有 $\min(n,k)$ 次有效操作。数组类型和大小确定。

由于我比较废，所以在给了初始化之后还建了一个访问数组，实际上可以改掉的。

对于每一个点的查询，有两种情况：

1.次数未用尽，可以继续修改；

2.次数已用尽，不可继续修改。

故分类讨论两种情况，对于每种情况取最大值，可以遍历每一种情况。

对于 1：

在本次修改扩大三倍，对左下、右下进行搜索。

对于 2：

在本次修改中不进行更改，对左下、右下进行搜索。

由于修改过后可能会存在下面修改更优的情况，将情况 2 置于情况 1 下方再次取一遍最大值即可，以表述当前位置保留操作次数不进行修改的情况。

代码如下：

#include<bits/stdc++.h>
using namespace std;
int n,k;
long long a[105][105];
long long f[105][105][105];//记忆化搜索数组 
bool v[105][105][105];//访问数组 
long long ans;
long long dfs(int i,int j,int p){
    if(i<0||i>n||j<0||j>n){//越界 
    	return 0;
	}
	if(v[i][j][p]){//查询过 
		return f[i][j][p];
	}
    else{
    	if(p!=k){//可继续修改 
    		f[i][j][p]=max(f[i][j][p],dfs(i+1,j,p+1)+a[i][j]*3);//修改至三倍 
    		f[i][j][p]=max(f[i][j][p],dfs(i+1,j+1,p+1)+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]);
    	v[i][j][p]=1;//标记访问 
		return f[i][j][p];
    }
}
int main(){
	scanf("%d%d",&n,&k);
	if(k>n){//有效操作次数下调 
		k=n;
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=i;j++){
			scanf("%lld",&a[i][j]);
		}
	}
	memset(f,-0x3f,sizeof(f));//初始化避免记忆化过程中修改取最大值时遇到比原数大的情况 
	ans=dfs(1,1,0);
	printf("%lld",ans);
	return 0;
}