11320: 【原1320】numtri

题目

题目描述

author: USACO 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1320

Description

Consider the number triangle shown below. Write a program that calculates the highest sum of numbers that can be passed on a route that starts at the top and ends somewhere on the base. Each step can go either diagonally down to the left or diagonally down to the right.

        7

      3   8

    8   1   0

  2   7   4   4

4   5   2   6   5

In the sample above, the route from 7 to 3 to 8 to 7 to 5 produces the highest sum: 30.

Input Format

The first line contains R (1 <= R <= 1000), the number of rows. Each subsequent line contains the integers for that particular row of the triangle. All the supplied integers are non-negative and no larger than 100.

Output Format

A single line containing the largest sum using the traversal specified.

Sample Input:

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

Sample Output:

30

BugenZhao's solution

//
// Created by BugenZhao on 2019/3/24.
//

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <map>
#include <cstring>

using namespace std;

int table[1005][1005];
int ans[1005][1005];

int main() {
    int R;
    cin >> R;

    for (int i = 0; i < R; ++i) {
        for (int j = 0; j <= i; ++j) {
            scanf("%d", &table[i][j]);
        }
    }

    ans[0][0] = table[0][0];
    for (int i = 1; i < R; ++i) {
        for (int j = 0; j <= i; ++j) {
            if (j == 0) ans[i][j] = ans[i - 1][j];
            else if (j == i) ans[i][j] = ans[i - 1][j - 1];
            else ans[i][j] = max(ans[i - 1][j - 1], ans[i - 1][j]);
            ans[i][j] += table[i][j];
        }
    }

    int maxAns = 0;
    for (int i = 0; i < R; ++i) {
        maxAns = max(maxAns, ans[R - 1][i]);
    }
    cout << maxAns << endl;
    return 0;
}

ligongzzz's solution

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

int val_data[1009][1009] = { 0 };
int n;

int dp_data[1009][1009] = { 0 };

int dp(int posi, int posj) {
    if (dp_data[posi][posj] >= 0)
        return dp_data[posi][posj];
    if (posi >= n)
        return 0;

    int ans1 = val_data[posi][posj] + dp(posi + 1, posj),
        ans2 = val_data[posi][posj] + dp(posi + 1, posj + 1);

    dp_data[posi][posj] = max(ans1, ans2);
    return dp_data[posi][posj];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n;

    memset(dp_data, -1, sizeof(dp_data));

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j <= i; ++j) {
            cin >> val_data[i][j];
        }
    }

    cout << dp(0, 0);

    return 0;
}

skyzh's solution

#include <iostream>
#include <cstdio>
using namespace std;

int MAP[1000][1000];
int dp[1000][1000] = { 0 };
int main() {
    int N;
    scanf("%d", &N);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j <= i; j++) {
            scanf("%d", &MAP[i][j]);
        }
    }
    dp[0][0] = MAP[0][0];
    for (int i = 1; i < N; i++) {
        dp[i][0] = dp[i - 1][0] + MAP[i][0];
        for (int j = 1; j < i; j++) {
            dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + MAP[i][j];
        }
        dp[i][i] = dp[i - 1][i - 1] + MAP[i][i];
    }
    int MAX = 0;
    for (int i = 0; i < N; i++) {
        MAX = max(dp[N - 1][i], MAX);
    }
    cout << MAX << endl;
    return 0;
}

yyong119's solution

#include <iostream>
#define MAX_R 1010
using namespace std;

int state[MAX_R][MAX_R], triangle[MAX_R][MAX_R];

int main() {

    ios::sync_with_stdio(false);

    int R; cin >> R;
    for (int i = 0; i < R; ++i)
        for (int j = 0; j <= i; ++j)
            cin >> triangle[i][j];
    for (int i = 0; i <= R - 1; ++i)
        state[R - 1][i] = triangle[R - 1][i];
    for (int i = R - 2; i >= 0; --i)
        for (int j = 0; j <= i; ++j)
            state[i][j] = (state[i + 1][j] > state[i + 1][j + 1] ? state[i + 1][j] : state[i + 1][j + 1]) + triangle[i][j];
    cout << state[0][0] << endl;

    return 0;
}