1 条题解

  • 0
    @ 2023-3-3 14:44:11

    道题是一道经典的动态规划问题,可以使用动态规划的思想来解决。以下是可能的算法流程:

    1. 定义一个二维数组 dp[i][j],其中 dp[i][j] 表示到达第 i 行第 j 列时所能得到的最大珠宝数目。
    2. 初始化第一行的值,即 dp[0][0] = a[0][0],对于第一行的其他列,有 dp[0][j] = dp[0][j-1] + a[0][j]
    3. 对于第 i 行(1 <= i < n),根据它的上一行 i-1 的结果,递推计算 dp[i][j] 的值。具体地,有以下两种情况:
      1. 如果 j == 0,即当前行的第一列,有 dp[i][j] = dp[i-1][j] + a[i][j]
      2. 如果 j > 0,即当前行的其他列,有 dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + a[i][j]
    4. 最终的答案是 max(dp[n-1][0], dp[n-1][1], ..., dp[n-1][n-1])

    以下是参考代码

    #include <iostream>
    #include <algorithm>
    using namespace std;
    
    const int MAXN = 105;   // 最大行数
    
    int a[MAXN][MAXN];      // 存储每行的珠宝数目
    int dp[MAXN][MAXN];     // dp[i][j] 表示到达第 i 行第 j 列时所能得到的最大珠宝数目
    
    int main()
    {
        int n;
        cin >> n;
    
        // 读入每行的珠宝数目
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j <= i; j++)
            {
                cin >> a[i][j];
            }
        }
    
        // 初始化第一行的值
        dp[0][0] = a[0][0];
        for (int j = 1; j < n; j++)
        {
            dp[0][j] = dp[0][j-1] + a[0][j];
        }
    
        // 递推计算 dp[i][j] 的值
        for (int i = 1; i < n; i++)
        {
            for (int j = 0; j <= i; j++)
            {
                if (j == 0)
                {
                    dp[i][j] = dp[i-1][j] + a[i][j];
                }
                else
                {
                    dp[i][j] = max(dp[i-1][j-1], dp[i-1][j]) + a[i][j];
                }
            }
        }
    
        // 找出最大值
        int ans = dp[n-1][0];
        for (int j = 1; j < n; j++)
        {
            ans = max(ans, dp[n-1][j]);
        }
    
        cout << ans << endl;
        return 0;
    }
    
    
    • 1

    信息

    ID
    1020
    时间
    1000ms
    内存
    128MiB
    难度
    10
    标签
    递交数
    1
    已通过
    1
    上传者