P1544 三倍经验

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