写的很乱, 记录一下, 希望后面再来优化

思路采用的是题解 题解 P1018 【乘积最大】, 给出了对应的haskell实现

module Main where

import Data.List
import Control.Monad.Reader
import Control.Monad.State
import qualified Data.Map as M
import Data.Maybe
import Debug.Trace

main :: IO ()
main = do
  [n, k] <- fmap read . words <$> getLine
  strIn <- getLine
  let aaaa = preprocessData n strIn
      bbbb = placeTheRemainingMultiplicationSign 2
      cccc = runReader (placeTheFirstMultiplicationSign $ n - k) aaaa
      dddd = flip runReader (aaaa, (n, k + 1)) . flip evalStateT cccc $ bbbb
  -- putStrLn . show $ aaaa
  -- putStrLn . show $ cccc
  putStrLn . show $ dddd

-- | Preprocessing to quickly find the number represented by a range string
--   for 1231
--   [((1,1),1),((1,2),12),((1,3),123),((1,4),1231),((2,2),2),((2,3),23),((2,4),231),((3,3),3),((3,4),31),((4,4),1)]
type PreCache = M.Map (Int, Int) Integer

preprocessData :: Int -> String -> PreCache
preprocessData length' str =
  M.fromList $
    zip
      [(x, y) | x <- [1 .. length'], y <- [x .. length']]
      [read $ drop i (take j str) | i <- [0 .. length' - 1], j <- [i + 1 .. length']]

-- | After the i-th character, place the j-th multiplication sign
type Cache = M.Map (Int {- i -}, Int {- j -}) Integer {- maximum -}

placeTheFirstMultiplicationSign :: Int -> Reader PreCache Cache
placeTheFirstMultiplicationSign length_of_str = ask >>= return . M.mapKeys (\(x, y) -> (y, x)) . M.filterWithKey (\k _ -> fst k == 1 && snd k <= length_of_str)

placeTheRemainingMultiplicationSign :: Int -> StateT Cache (Reader (PreCache, (Int {- n -}, Int {- k -}))) Integer
placeTheRemainingMultiplicationSign layer = do
  (_, (_, total_number_of_multipliers)) <- ask
  if layer > total_number_of_multipliers
    then do get >>= return . maximum . M.filterWithKey (\k _ -> snd k == total_number_of_multipliers) -- . (flip trace <*> show)
    else do placeTheRemainingMultiplicationSign' layer
            placeTheRemainingMultiplicationSign $ layer + 1

placeTheRemainingMultiplicationSign' :: Int -> StateT Cache (Reader (PreCache, (Int {- n -}, Int {- k -}))) ()
placeTheRemainingMultiplicationSign' layer = do
  (_, (length_of_string, _)) <- ask
  foldl' (\x y-> x >> (placeTheRemainingMultiplicationSign'' layer y)) (return ()) [layer .. length_of_string]

placeTheRemainingMultiplicationSign'' :: Int -> Int -> StateT Cache (Reader (PreCache, (Int {- n -}, Int {- k -}))) ()
placeTheRemainingMultiplicationSign'' layer cur_place = do
  (pre_cache, (length_of_string, _)) <- ask
  cache <- get
  let cur_max =
        foldl'
          ( \x pre_place ->
              max x $
                -- (flip trace <*> shows "cal_value: " . show) $
                  (fromMaybe 0 $ {- (flip trace <*> shows " cache: " . shows cache . shows "pre_value: " . show) $ -} M.lookup ((fromInteger pre_place), layer - 1) cache) * (fromMaybe 0 $ {- (flip trace <*> showString "\npre_place: " . shows pre_place . shows ", layer: " . shows layer . shows ", cur: " . shows cur_place . shows ", " . show) $ -} (M.lookup ((fromInteger pre_place) + 1, cur_place) pre_cache))
          )
          (0 :: Integer)
          ([(toInteger layer) - 1 .. (toInteger $ length_of_string)])
  modify $ M.insert (cur_place, layer) cur_max