AcWing 275. 传纸条 (JavaScript )
原题链接
中等
作者:
cp777
,
2021-03-07 11:04:45
,
所有人可见
,
阅读 225
const N = 60;
let f = [];
for (let i = 0; i < 2 * N; i++) f[i] = new Array(N);
for (let i = 0; i < 2 * N; i++) {
for (let j = 0; j < N; j++) {
f[i][j] = new Int32Array(N);
}
}
let g = [];
g.push('');
let n = 0,
m = 0;
let buf = '';
process.stdin.on('readable', function () {
let chunk = process.stdin.read();
if (chunk) buf += chunk.toString();
});
let getInputNums = line => line.split(' ').filter(s => s !== '').map(x => parseInt(x));
let getInputStr = line => line.split(' ').filter(s => s !== '');
process.stdin.on('end', function () {
buf.split('\n').forEach(function (line, lineIdx) {
if (lineIdx === 0) {
n = getInputNums(line)[0];
m = getInputNums(line)[1];
} else if (lineIdx <= n) {
let arr = getInputNums(line);
arr.unshift(0);
g.push(arr);
if (lineIdx === n) {
for (let k = 2; k <= m + n; k++) { // k = i1 + j1
for (let i1 = 1; i1 <= n; i1++) {
for (let i2 = 1; i2 <= n; i2++) {
let j1 = k - i1,
j2 = k - i2;
if (j1 >= 1 && j1 <= m && j2 >= 1 && j2 <= m) {
let t = g[i1][j1];
if (i1 !== i2) t += g[i2][j2]; //没有走到同一个点
f[k][i1][i2] = Math.max(f[k][i1][i2], f[k - 1][i1 - 1][i2 - 1] + t);
f[k][i1][i2] = Math.max(f[k][i1][i2], f[k - 1][i1 - 1][i2] + t);
f[k][i1][i2] = Math.max(f[k][i1][i2], f[k - 1][i1][i2 - 1] + t);
f[k][i1][i2] = Math.max(f[k][i1][i2], f[k - 1][i1][i2] + t);
}
}
}
}
console.log(f[n+m][n][n]);
}
}
});
});