AcWing 898. 数字三角形
原题链接
简单
作者:
唱跳Rap篮球
,
2021-12-14 14:20:15
,
所有人可见
,
阅读 243
const readline = require('readline')
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
})
let K = 0
let n;
const a = new Array(510).fill(0).map(v => new Array(510).fill(0))
const f = new Array(510).fill(0).map(v => new Array(510).fill(-Infinity))
rl.on('line',function(line){
if(K === 0) {
n = parseInt(line)
}else{
const arr = line.split(' ').map(v => parseInt(v))
for(let i = 0;i < arr.length;i++){
a[K][i + 1] = arr[i]
}
}
K++
})
rl.on('close',function(){
f[1][1] = a[1][1]
// console.log(f[1][1])
for(let i = 2;i <= n;i++){
for(let j = 1;j <= i;j++){
f[i][j] = Math.max(f[i - 1][j - 1] + a[i][j],f[i - 1][j] + a[i][j])
}
}
let res = -Infinity
for(let i = 1;i <= n;i++){
res = Math.max(res,f[n][i])
}
console.log(res)
})