haskell没有vector求助
查看原帖
haskell没有vector求助
625398
_OTZ_楼主2024/10/3 13:26

提交后编译报错,找不到vector

查询 在线评测 | 洛谷帮助中心 得知没有 vector package 库,请问大佬们有什么好的替代


module Main where

import Control.Monad (replicateM)
import Control.Monad.Reader
import Control.Monad.State
import Data.List (foldl1')
import qualified Data.Map as M
import Data.Maybe (fromMaybe)
import qualified Data.Vector as V

main :: IO ()
main = do
  [n, _] <- fmap read . words <$> getLine
  sum <$> replicateM n
      ( flip evalState mempty
          . runReaderT processRow
          . V.fromList
          . fmap read . words <$> getLine
      )
    >>= print

type Interval = (Int, Int)

type Cache = M.Map Interval Integer

processRow :: ReaderT (V.Vector Int) (State Cache) Integer
processRow = ask >>= processRow' . V.length

processRow' :: Int -> ReaderT (V.Vector Int) (State Cache) Integer
processRow' lengthOfInterval
  | lengthOfInterval >= 0 = do
      row <- ask
      let intervalToCalculate = zip [(1 :: Int) ..] [lengthOfInterval .. V.length row]
      _ <- foldl1' (>>) $ processRow'' <$> intervalToCalculate
      processRow' $ lengthOfInterval - 1
  | lengthOfInterval == -1 = get >>= {-trace . show <*>-} return . maximum
  | otherwise = undefined

processRow'' :: Interval -> ReaderT (V.Vector Int) (State Cache) Integer
processRow'' interval@(left, right) = do
  row <- ask
  cache <- get
  let lengthOfInterval = V.length row - (right - left + 1)
      max' = case lengthOfInterval == 0 of
        False ->
          max
            ((lookup' (left - 1, right) cache) + (toInteger (getByIndex row $ left - 1)) * 2 ^ lengthOfInterval)
            ((lookup' (left, right + 1) cache) + (toInteger (getByIndex row $ right + 1)) * 2 ^ lengthOfInterval)
        True -> 0
  modify (M.insert interval max')
  return max'
  where
    lookup' interval' cache = fromMaybe 0 $ M.lookup interval' cache
    getByIndex row index = if index > 0 && index <= V.length row then row V.! (index - 1) else 0

2024/10/3 13:26
加载中...