torus711 のアレ

主に競技プログラミングの問題について書きます

Codeforces #162, Division 2, B : Roadside Trees (Simplified Edition)

概要

道沿いに n 本の木が生えており、それぞれの頂点にナッツがある。
はじめ、Liss は一番目の木の根元におり、以下の行動ができる。

  • (木の頂点で)その場にあるナッツを食べる
  • 高さの一単位分、木を昇降する
  • 次の木の同じ高さの場所に飛び移る

ただし、次の木の高さより高い場所にいるとき、次の木に飛び移ることはできない。
それぞれの木の高さの情報が与えられるので、全てのナッツを食べるために必要な工程数を求めよ。

解法

そのままシミュレーションします。
ちなみに、木の高さに関する制約は無視しても構いません。
(昇降してから移動するのと、仮想的な木に移動してから昇降するのは同じ)

コード

import Control.Applicative
import Control.Monad
import Data.List

main = do
	n <- read <$> getLine
	hs <- replicateM n $ read <$> getLine
	print $ solve hs 0 0

solve :: [Int] -> Int -> Int -> Int
solve [] _ res = res - 1
solve (c:hs) h res = solve hs c ( res + abs ( c - h ) + 2 )