41 lines
1 KiB
Haskell
41 lines
1 KiB
Haskell
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
|