AtCoder Beginner Contest 408 D

https://atcoder.jp/contests/abc408/tasks/abc408_d

単なるDPですね。変更後で、まだ一度も0になっていない、1続行中、前に1になって0続行中、の3つの状態が考えられて、値を変更回数とします。

// Flip to Gather
#![allow(non_snake_case)]


//////////////////// 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()
}


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

use std::cmp::min;

type DP = [i32; 3];

fn update_DP(dp: DP, c: char) -> DP {
    if c == '0' {
        [dp[0], min(dp[0]+1, dp[1]+1), min(dp[1], dp[2])]
    }
    else {
        [dp[0]+1, min(dp[0], dp[1]), min(dp[1], dp[2]+1)]
    }
}

fn F_each() -> i32 {
    let N: i32 = read();
    let S: String = read();
    let mut dp: DP = [0, N, N];
    for c in S.chars() {
        dp = update_DP(dp, c)
    }
    *dp.iter().min().unwrap()
}

fn F(T: usize) {
    for _ in 0..T {
        println!("{}", F_each())
    }
}

fn main() {
    let T: usize = read();
    F(T)
}