AtCoder Beginner Contest 346 D

https://atcoder.jp/contests/abc346/tasks/abc346_d

文字列を左から見ていって、位置と直前の文字と隣が同じだったことが何回あるかを状態としてDPします。

// Gomamayo Sequence
#![allow(non_snake_case)]

use std::cmp::min;


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect()
}


//////////////////// process ////////////////////

fn read_input() -> (String, Vec<i64>) {
    let _N: usize = read();
    let S: String = read();
    let C: Vec<i64> = read_vec();
    (S, C)
}

type DP = [i64; 4];
const INF: i64 = 1e18 as i64;

fn initialize_dp(d: u8, cost: i64) -> DP {
    if d == 0 {
        [0, cost, INF, INF]
    }
    else {
        [cost, 0, INF, INF]
    }
}

fn update_dp(d: u8, cost: i64, dp: DP) -> DP {
    let mut new_dp: DP = [INF; 4];
    let ud: usize = d as usize;
    for i in 0..4 {
        let prev = i & 1;
        let num_conts = i >> 1;
        for new_ud in 0..2 {
            let num_conts1 = num_conts + if new_ud == prev { 1 } else { 0 };
            if num_conts1 < 2 {
                let new_i = new_ud | (num_conts1 << 1);
                let new_cost = dp[i] + if new_ud == ud { 0 } else { cost };
                new_dp[new_i] = min(new_cost, new_dp[new_i])
            }
        }
    }
    new_dp
}

fn F(S: String, C: Vec<i64>) -> i64 {
    let ds: Vec<u8> = S.chars().map(|c| (c as u8) - 48).collect();
    let mut dp: DP = initialize_dp(ds[0], C[0]);
    for i in 1..ds.len() {
        dp = update_dp(ds[i], C[i], dp)
    }
    min(dp[2], dp[3])
}

fn main() {
    let (S, C) = read_input();
    println!("{}", F(S, C))
}