SoundHound Inc. Programming Contest 2018 (春) D - 建物
問題
解法
(i, j) から (i, k) に移動して (i+1, k) に移動する経路 (i, j) => (i+1, k) を考える。このとき、 (i, j-1) => (i+1, k) よりも多くの報酬が得られることに留意する。次に (i+1, k+1) に移動する経路を考える。このとき (i, j-1) => (i+1, k+1) よりも (i, j) => (i+1, k+1) の方がより多くの報酬が得られる。このように、下の階から上の階へ上がる経路はしゃくとり法によって求まる。
コード
use std::cmp; use std::i64::MIN; fn main() { let (h, w) = { let v = read_values::<usize>(); (v[0], v[1]) }; let p = { let mut p = vec![vec![0; w]; h + 1]; for i in 0..h { let v = read_values::<i64>(); for j in 0..w { p[i][j] = v[j]; } } p }; let f = { let mut f = vec![vec![0; w]; h + 1]; for i in 0..h { let v = read_values::<i64>(); for j in 0..w { f[i][j] = v[j]; } } f }; let mut gain = vec![vec![MIN; w]; h + 1]; gain[0][0] = p[0][0]; for i in 0..h { let mut left_turn = vec![0; w]; for j in 1..w { left_turn[j] = cmp::max(left_turn[j - 1] + p[i][j - 1] - (f[i][j - 1] + f[i][j]), 0); } let mut right_turn = vec![0; w]; for j in (0..(w - 1)).rev() { right_turn[j] = cmp::max(right_turn[j + 1] + p[i][j + 1] - (f[i][j + 1] + f[i][j]), 0); } let mut sum = vec![0; w + 1]; for j in 0..w { sum[j + 1] = sum[j] + p[i][j] - f[i][j]; } if i == 0 { for j in 0..w { gain[i + 1][j] = p[i + 1][j] - f[i + 1][j] + sum[j + 1] + right_turn[j]; } } else { let mut left_max = 0; for j in 0..w { let segment_sum = sum[j + 1] - sum[left_max + 1]; let enter_gain = p[i + 1][j] - f[i + 1][j]; let old_gain = gain[i][left_max] + segment_sum + left_turn[left_max]; let new_gain = gain[i][j] + left_turn[j]; if old_gain < new_gain { left_max = j; } gain[i + 1][j] = cmp::max(old_gain, new_gain) + right_turn[j] + enter_gain; } let mut right_max = w - 1; for j in (0..w).rev() { let segment_sum = sum[right_max] - sum[j]; let enter_gain = p[i + 1][j] - f[i + 1][j]; let old_gain = gain[i][right_max] + segment_sum + right_turn[right_max]; let new_gain = gain[i][j] + right_turn[j]; if old_gain < new_gain { right_max = j; } gain[i + 1][j] = cmp::max( cmp::max(old_gain, new_gain) + left_turn[j] + enter_gain, gain[i + 1][j], ); } } } for i in 0..w { println!("{}", gain[h][i]); } } fn read_line() -> String { let stdin = std::io::stdin(); let mut buf = String::new(); stdin.read_line(&mut buf).unwrap(); buf } fn read_values<T>() -> Vec<T> where T: std::str::FromStr, T::Err: std::fmt::Debug, { read_line() .split(' ') .map(|a| a.trim().parse().unwrap()) .collect() }