AtCoder Beginner Contest 344 D

https://atcoder.jp/contests/abc344/tasks/abc344_d

単なるDPですね。どこまで一致したかが状態で、そのなかで最小の金額を記憶しておきます。

// String Bags
#![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()
}


//////////////////// Bag ////////////////////

type Bag = Vec<String>;

fn read_bag() -> Bag {
    let mut v: Vec<String> = read_vec();
    v.remove(0);
    v
}


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

fn read_input() -> (String, Vec<Bag>) {
    let T: String = read();
    let N: usize = read();
    let bags: Vec<Bag> = (0..N).map(|_| read_bag()).collect();
    (T, bags)
}

fn initialize_dp(L: usize) -> Vec<i32> {
    let mut dp: Vec<i32> = vec![-1; L+1];
    dp[0] = 0;
    dp
}

fn update_dp(bag: Bag, dp: Vec<i32>, T: &String) -> Vec<i32> {
    let mut new_dp: Vec<i32> = dp.to_vec();
    for (i, n) in dp.into_iter().enumerate() {
        if n == -1 {
            continue
        }
        for s in bag.iter() {
            let j = i + s.len();
            if j <= T.len() && s == &T[i..j] {
                if new_dp[j] == -1 {
                    new_dp[j] = n + 1
                }
                else {
                    new_dp[j] = min(new_dp[j], n + 1)
                }
            }
        }
    }
    new_dp
}

fn F(T: String, bags: Vec<Bag>) -> i32 {
    let L = T.len();
    let mut dp = initialize_dp(L);
    for bag in bags.into_iter() {
        dp = update_dp(bag, dp, &T)
    }
    dp[L]
}

fn main() {
    let (T, bags) = read_input();
    println!("{}", F(T, bags))
}