P1544 三倍经验 题解

· · 题解

题意已经很清楚了，不再赘述。

解题思路

先不考虑乘三倍的情况。
将金字塔中每一个数看作一个点。

我们用 dp_{i,j} 来表示走到第 i 行第 j 个点时走过的最大得分。
因为点（i,j）是从点（i - 1, j）和点（i - 1,j - 1）走来，所以易得状态转移方程式：

dp_{i,j} = \max(dp_{i - 1,j}, dp_{i - 1, j - 1}) + a_{i, j}

然后考虑乘三倍的情况。
用 dp_{i,j,l} 来表示走到第 i 行第 j 个点，乘 l 次三倍时走过的最大得分。 结合不考虑乘三倍情况的状态转移方程式，易得最终状态转移方程式：

dp_{i, j, l} = \begin{cases} dp_{i, j, l} = \max(dp_{i - 1, j, l}, dp_{i - 1, j - 1, l}) + a_{i, j}, (l = 0) \\ dp_{i, j, l} = \max(dp_{i, j ,l}, dp_{i - 1, j, l - 1} + a_{i, j} \times 3, dp_{i - 1, j - 1, l - 1} + a_{i, j} \times 3), \text{Otherwise.} \end{cases}

以上是代码核心部分。 在搜索时要记得套两层循环（j 和 k），应为存在负数，所以不是乘三倍的次数越多越好。

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;

最后要记得在开始时把数组初始化。

AC 代码

#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;
}