白駿1932号:整数三角形


質問する


題ショートカットキー>白駿1932号:整数三角形

に答える


下から上への和を最大の経路とする.
import sys
n = int(input())
tri = [list(map(int, sys.stdin.readline().rstrip().split())) for _ in range(n)]
for i in range(n-2, -1, -1):
    for j in range(i+1):
        tri[i][j]+=max(tri[i+1][j] ,tri[i+1][j+1])
print(tri[0][0])

コードの改良


以下の関数形式で記述し,時間をさらに短縮した.
def solution():
    import sys
    n = int(sys.stdin.readline())
    tri = [list(map(int, sys.stdin.readline().rstrip().split())) for _ in range(n)]
    for i in range(n-2, -1, -1):
        for j in range(i+1):
            tri[i][j]+=max(tri[i+1][j] ,tri[i+1][j+1])
    print(tri[0][0])
solution()

c++を使用して解く

#include<iostream>
using namespace std;

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); 
    int n; cin>>n;
    int tri[n+1][n+1]={};
    for(int i=0; i<n; i++){
        for(int j=0; j<i+1; j++){
            cin>>tri[i][j];
        }
    }
    for(int i=n-2; -1<i; i--){
        for(int j=0; j<i+1; j++){
            tri[i][j] = tri[i][j]+max(tri[i+1][j], tri[i+1][j+1]);
        }
    }
    cout << tri[0][0];
}