P1544 三倍经验 （记忆化搜索）

三倍经验

题目描述

数字金字塔由 $n$ 行整数组成，第 $i(1\le i\le n)$ 行有 $i$ 个数字，一个示例如下。

        7
      3   9
    8   1   0
  2   7   4   4 
4   5   2   6   5

现在你在金字塔的顶部（第一行），你希望走到金字塔的底部（第 $n$ 行），每一步你只能走向当前所在位置的左下方的数字或者右下方的数字。同时作为一个强大的小朋友，你可以选择金字塔中的不多于 $k$ 个数字让他们成为原来的 $3$ 倍。

你会收集你路上经过的所有位置上的数字，最后的得分即为收集的数字之和，求最大得分。

输入格式

第一行输入两个整数 $n,k$，表示数字金字塔的行数和乘 $3$ 的数字个数最大值；
接下来 $n$ 行，其中的第 $i$ 行有 $i$ 个以空格隔开的整数依次表示数字金字塔第 $i$ 行的数字 $a_{i,1},a_{i,2},a_{i,3}...a_{i,i}$。

输出格式

一行一个整数，表示最大得分。

样例 #1

样例输入 #1

5 3
7
3 9
8 1 0
2 7 4 4
4 5 2 6 5

样例输出 #1

75

提示

对于 $30\%$ 的数据，满足 $k\le n\le 6$，并且对于任意 $1\le i\le n$，$1\le j\le i$ 满足 $0\le a_{i,j}\le 100$；
对于 $100\%$ 的数据，满足 $1\le n\le 100$，$0\le k\le \frac{n(n+1)}{2}$，且对于任意 $1\le i\le n$，$1\le j\le i$ 满足 $|a_{i,j}|\le 10^9$。

首先可以知道这道题和dp三角形模型有点关系，所以我们可以先知道对于三角形模型的状态转移是由左下和右下的最大值转移过来。

但是对于这道题给我们加入了一个条件，也就是我们能任选k个数进行乘三操作，这时候会有两个想法。

第一个想法是按照之前的方法进行搜索并且记录下路径，对路径上最大的三个数进行乘三操作，当然这个想法是错误的。

第二个想法是给dp数组多加一个维度，这里可以这样理解，对于要乘的k个数，我们其实很难进行搜索出来，所以我们就可以多加一个维度来代表这个数是乘三还是不乘三，这样就能够使用dp数组表示出来这个情况。

那么这时候就可以得到：f[i][j][times]代表在点$(i,j)$并且剩余乘三次数为$times$次的情况下能够得到的最大的数值。

然后再进行记忆化搜索就很容易了，但是这里要注意一个小点，原题给出的三角形中的数据是有可能为负数的，所以我们要把dp数组初始化为负无穷，这个时候我们就必须要多设立一个判重数组进行判重了。

#include <bits/stdc++.h>
using namespace std;
const int N = 110;
const int mod = 1e9 + 7;
const int Mod = 1e9 + 7;
#define int long long

int n,k;
int g[N][N];
int f[N][N][N];
bool vis[N][N][N];

int dfs(int i,int j,int times){
    if(vis[i][j][times])return f[i][j][times];
    vis[i][j][times] = 1;
    if(i == n){
        if(times){
            f[i][j][times] = max(g[i][j],g[i][j]*3);
        }
        else f[i][j][times] = g[i][j];
        return f[i][j][times];
    }

    if(times){
        f[i][j][times] = max(f[i][j][times],dfs(i+1,j+1,times - 1) + g[i][j]*3);
        f[i][j][times] = max(f[i][j][times],dfs(i+1,j,times - 1) + g[i][j]*3);
    }
    f[i][j][times] = max(f[i][j][times],dfs(i+1,j+1,times) + g[i][j]);
    f[i][j][times] = max(f[i][j][times],dfs(i+1,j,times) + g[i][j]);
    return f[i][j][times];
}

void solve(int times)
{
    cin >> n >> k;
    memset(f,-0x3f,sizeof f);
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= i;j++){
            cin >> g[i][j];
        }
    }

    dfs(1,1,k);

    int ans = f[1][1][k];

    cout << ans << endl;
}

signed main()
{
    int T;
    // cin >> T;
    T = 1;
    for (int i = 1; i <= T; i++)
    {
        solve(i);
    }

    return 0;
}