[Leaf] P1544 三倍经验

p1544-三倍经验---洛谷">P1544 三倍经验 - 洛谷

1. 题面梗概

中译中：在一个数字金字塔中从顶走到低，求路径最大和。特殊规则：你有 $k$ 次机会让路径上的某个数字变成其 3 倍。

$1 \le n \le 100, 0 \le k \le \frac{n(n+1)}{2}$，每个数可能为负数。

2. 逻辑推导

如果没有 $k$ 的限制，这就是普通的数字金字塔 DP。

现在的难点在于：每一层除了向 “左下” 和 “右下” 走以外，还有一个 “翻倍” 的决策。

那么我们只需要把 翻倍看作一个技能，把技能的使用次数加入阶段就行。

2.1 状态

定义：$f[i][j][k]$ 为从 $(i, j)$ 走到 最底层，恰好使用了 $k$ 次技能的最大得分。

原始转移：

$$f[i][j] = \max( f[i-1][j], f[i-1][j-1] ) + a[i][j]$$

那么加上技能后的转移：

1. 不使用技能

$$f[i][j][k] = max( f[i-1][j][k], f[i-1][j-1][k] ) + a[i][j]$$

2. 使用技能 ( 限制 $k \ge 1$ )

$$f[i][j][k] = max( f[i-1][j][k-1], f[i-1][j-1][k-1] ) + 3a[i][j]$$

3. 代码实现

▶

AcCode

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int maxn = 100 + 5;
const ll inf = 1e18;

ll f[maxn][maxn][maxn];
// f[i][j][k] -> 走到 (i, j) 用了 k 次 *3 的 最大得分
ll a[maxn][maxn];
int n, kk;

int main( )
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n >> kk;
    for( int i = 1; i <= n; ++ i )
    {
        for( int j = 1; j <= i; ++ j )
        {
            cin >> a[i][j];
        }
    }

    for( int j = 1; j <= n; ++ j )
    {
        f[n][j][0] = a[n][j], f[n][j][1] = a[n][j] * 3;
        for( int k = 2; k <= kk; ++ k ) f[n][j][k] = -inf;
    }

    for( int i = n - 1; i >= 1; -- i )
    {
        for( int j = 1; j <= i; ++ j )
        {
            for( int k = 0; k <= kk; ++ k )
            {
                f[i][j][k] = max( f[i+1][j][k], f[i+1][j+1][k] ) + a[i][j];
                if( k >= 1 ) f[i][j][k] = max( f[i][j][k], 
                    max( f[i+1][j][k-1], f[i+1][j+1][k-1] ) + a[i][j] * 3 );
            }
        }
    }

    ll ans = -inf;
    for( int k = 0; k <= kk; ++ k ) ans = max( ans, f[1][1][k] );
    cout << ans << '\n';
    return 0;
}

4. 复盘

• 复杂度分析：$O( n^2 \cdot k )$。

• 碎碎念：这个类似于图论的分层图操作；最开始我是从最顶上向下递推的，但是发现最后统计答案太麻烦了，所以倒着从下往上推答案，这样虽然不直观，但是答案一定在 $(1, 1)$ 这个点上。

• 关联笔记：线性DP