Submission #156176

---

Source Code Expand

{-# LANGUAGE BangPatterns #-}

import           Control.Applicative
import           Control.Monad
import qualified Data.ByteString.Char8 as S
import           Data.List
import           Data.Maybe
import           Text.Printf
import Data.Vector.Generic ((!))
import qualified Data.Vector as V
import qualified Data.Vector.Unboxed as U
import qualified Data.Vector.Unboxed.Mutable as UM
import Data.STRef

-- util

getInts :: IO [Int]
getInts = catMaybes . map (fmap fst . S.readInt) . S.words <$> S.getContents

getInt :: IO Int
getInt = fst . fromJust . S.readInt <$> S.getLine

-- main

main :: IO ()
main = do
  n <- getInt
  ns <- getInts
  print $ n + 1 - lcs ns

lcs :: [Int] -> Int
lcs xs = max 1 $ U.maximum tbl where
  v = U.fromList $ 0 : xs
  n = U.length v

  tbl = U.create $ do
    r <- UM.replicate (n+1) 0
    UM.write r 0 1
    forM_ [1..n-1] $ \i -> do
      m <- newSTRef 0
      forM_ [0..i-1] $ \j -> do
        when (v!i > v!j) $ do
          p <- UM.read r j
          modifySTRef m $ max (p+1)
      UM.write r i =<< readSTRef m
    return r

{-
lcs xs = f (-1) 0 where
  v = V.fromList xs
  n = V.length v
  tbl =
    V.generate (n+1) $ \i -> do
    V.generate (n+1) $ \j -> do
      f (i-1) j

  f !prev !cur
    | cur >= n = 0
    | prev >= 0 && (v!prev) > (v!cur) = tbl!(prev+1)!(cur+1)
    | otherwise =
      max (tbl!(prev+1)!(cur+1)) (1+(tbl!(cur+1)!(cur+1)))
-}

Submission Info

Judge Result