ABC233 G - Strongest Takahashi

atcoder.jp

空行はスキップして良いという発想も大事だが、そもそも全ての長方形領域を列挙した O(N⁴) もそこまで大きくないというのに気付かなかった。

|rust| const INF: i64 = 1 << 60; fn main() { let (r, w) = (std::io::stdin(), std::io::stdout()); let mut sc = IO::new(r.lock(), w.lock());

let n: usize = sc.read();
let map: Vec<Vec<char>> = (0..n).map(|_| sc.chars()).collect();

let mut dp = vec![vec![vec![vec![INF; n + 1]; n]; n + 1]; n];

let ans = calc(&map, 0, n, 0, n, &mut dp);
println!("{}", ans);

}

fn calc( map: &Vec<Vec>, r_from: usize, r_to: usize, c_from: usize, c_to: usize, memo: &mut Vec<Vec<Vec<Vec>>>, ) -> i64 { let dr = r_to - r_from; let dc = c_to - c_from; if dr.min(dc) == 0 { return 0; } if memo[r_from][r_to][c_from][c_to] < INF { return memo[r_from][r_to][c_from][c_to]; }

let mut min_cost = dr.max(dc) as i64;
for i in r_from..r_to {
    if (c_from..c_to).all(|j| map[i][j] == '.') {
        let head = calc(map, r_from, i, c_from, c_to, memo);
        let tail = calc(map, i + 1, r_to, c_from, c_to, memo);
        min_cost = min_cost.min(head + tail);
    }
}

for j in c_from..c_to {
    if (r_from..r_to).all(|i| map[i][j] == '.') {
        let left = calc(map, r_from, r_to, c_from, j, memo);
        let right = calc(map, r_from, r_to, j + 1, c_to, memo);
        min_cost = min_cost.min(left + right);
    }
}

memo[r_from][r_to][c_from][c_to] = min_cost;
min_cost

}

pub struct IO<R, W: std::io::Write>(R, std::io::BufWriter);

impl<R: std::io::Read, W: std::io::Write> IO<R, W> { pub fn new(r: R, w: W) -> IO<R, W> { IO(r, std::io::BufWriter::new(w)) } pub fn write<S: ToString>(&mut self, s: S) { use std::io::Write; self.1.write_all(s.to_string().as_bytes()).unwrap(); } pub fn read<T: std::str::FromStr>(&mut self) -> T { use std::io::Read; let buf = self .0 .by_ref() .bytes() .map(|b| b.unwrap()) .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r' || b == b'\t') .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r' && b != b'\t') .collect::<Vec<>>(); unsafe { std::str::from_utf8_unchecked(&buf) } .parse() .ok() .expect("Parse error.") } pub fn usize0(&mut self) -> usize { self.read::() - 1 } pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec { (0..n).map(|| self.read()).collect() } pub fn chars(&mut self) -> Vec { self.read::().chars().collect() } }

||<