AtCoder Beginner Contest 315 F

https://atcoder.jp/contests/abc315/tasks/abc315_f

ただのDPですね。ただし、状態は位置番号とCです。Cはなので、DPの計算量はです。

// Prerequisites
#![allow(non_snake_case)]

use std::cmp::min;
use std::ops::{Add, Sub};


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


//////////////////// Point ////////////////////

#[derive(Clone, Copy)]
#[derive(PartialEq, Eq, Hash)]
struct Point {
    x: i64,
    y: i64,
}

impl Add for Point {
    type Output = Self;
    
    fn add(self, other: Self) -> Self {
        Self { x: self.x + other.x, y: self.y + other.y }
    }
}

impl Sub for Point {
    type Output = Self;
    
    fn sub(self, other: Self) -> Self {
        Self { x: self.x - other.x, y: self.y - other.y }
    }
}

impl Point {
    fn new(x: i64, y: i64) -> Point {
        Point { x, y }
    }
    
    fn length(&self) -> f64 {
        ((self.x * self.x + self.y * self.y) as f64).sqrt()
    }
    
    fn read() -> Point {
        let v: Vec<i64> = read_vec();
        Point::new(v[0], v[1])
    }
}


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

fn read_input() -> Vec<Point> {
    let N: usize = read();
    (0..N).map(|_| Point::read()).collect::<Vec<_>>()
}

fn g(points: &Vec<Point>) -> f64 {
    points.windows(2).map(|pts| (pts[0] - pts[1]).length()).sum::<f64>()
}

fn find_max_C(d: f64) -> usize {
    if d < 2.0 {
        1
    }
    else {
        find_max_C(d/2.0) + 1
    }
}

fn f(points: Vec<Point>) -> f64 {
    let N = points.len();
    let upper_dist = g(&points);
    let max_C = find_max_C(upper_dist);
    let mut dp: Vec<Vec<f64>> = (0..N).map(|_| vec![1e9; max_C+1]).collect();
    dp[0][0] = 0.0;
    for i in 1..N {
        for C in 0..min(max_C, i-1)+1 {
            let j0 = if C > i { 0 } else { i-C-1 };
            dp[i][C] = (j0..i).
                        map(|j| dp[j][C+1+j-i]+(points[i]-points[j]).length()).
                        min_by(|a, b| a.partial_cmp(b).unwrap()).unwrap();
        }
    }
    dp[N-1].iter().enumerate().
        map(|(C, d)| if C==0 { *d } else { d+2.0_f64.powf((C-1) as f64) }).
        min_by(|a, b| a.partial_cmp(b).unwrap()).unwrap()
}


//////////////////// main ////////////////////

fn main() {
    let pairs = read_input();
    println!("{}", f(pairs))
}