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