content: import Data.List (elemIndex)
  import Data.Char (chr, ord)
  import Data.Maybe (fromJust)
  
  mats :: [[Int]]
  mats =
    [ [5, 6, 3, 1]
    , [1, 5, 25, 30, 100, 70, 2, 1, 100, 250, 1, 1000, 2]
    , [1000, 1, 500, 12, 1, 700, 2500, 3, 2, 5, 14, 10]
    ]
  
  cost :: [Int] -> Int -> Int -> (Int, Int)
  cost a i j
    | i < j =
      let m =
            [ fst (cost a i k) + fst (cost a (k + 1) j) +
             (a !! i) * (a !! (j + 1)) * (a !! (k + 1))
            | k <- [i .. j - 1] ]
          mm = minimum m
      in (mm, fromJust (elemIndex mm m) + i)
    | otherwise = (0, -1)
  
  optimalOrder :: [Int] -> Int -> Int -> String
  optimalOrder a i j
    | i < j =
      let c = cost a i j
      in "(" ++ optimalOrder a i (snd c) ++ optimalOrder a (snd c + 1) j ++ ")"
    | otherwise = [chr ((+ i) $ ord 'a')]
  
  printBlock :: [Int] -> IO ()
  printBlock v =
    let c = cost v 0 (length v - 2)
    in putStrLn
         ("for " ++
          show v ++
          " we have " ++
          show (fst c) ++
          " possibilities, z.B " ++ optimalOrder v 0 (length v - 2))
  
  main :: IO ()
  main = mapM_ printBlock mats
  