1 条题解

  • 0
    @ 2022-12-25 15:29:55

    记忆化搜索

    #include <bits/stdc++.h>
    using namespace std;
    int r;
    int a[1005][1005];
    
    // 走到 (x,y) 的最大值
    int book[1005][1005];
    int f(int x, int y)
    {
        if (book[x][y] != -1)
            return book[x][y];
        if (x == 1 && y == 1)
            return book[x][y] = a[x][y];
        if (y == 1)
            return book[x][y] = f(x - 1, y) + a[x][y];
        if (y == x)
            return book[x][y] = f(x - 1, y - 1) + a[x][y];
        return book[x][y] = max(f(x - 1, y), f(x - 1, y - 1)) + a[x][y];
    }
    int main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
        cin >> r;
        for (int i = 1; i <= r; i++)
            for (int j = 1; j <= i; j++)
            {
                cin >> a[i][j];
                book[i][j] = -1;
            }
        int ans = 0;
        for (int j = 1; j <= r; j++)
            ans = max(ans, f(r, j));
        cout << ans;
        return 0;
    }
    

    自己找到顺序递推

    #include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    
    int n, ans;
    int a[1005][1005];
    //dp[i][j] 从(1,1)走到(i,j)位置和的最大值
    int dp[1005][1005];
    int main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
        cin >> n;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= i; j++)
                cin >> a[i][j];
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= i; j++)
                if (i == 1)
                    dp[i][j] = a[i][j];
                else if (j == 1)
                    dp[i][j] = dp[i - 1][j] + a[i][j];
                else if (j == i)
                    dp[i][j] = dp[i - 1][j - 1] + a[i][j];
                else
                    dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + a[i][j];
        ans = -1;
        for (int j = 1; j <= n; j++)
            ans = max(ans, dp[n][j]);
        cout << ans << endl;
        return 0;
    }
    
    • 1

    1.5.1 [IOI1994]数字三角形 Number Triangles

    信息

    ID
    941
    时间
    1000ms
    内存
    125MiB
    难度
    3
    标签
    递交数
    50
    已通过
    28
    上传者