26 lines
1.0 KiB
Haskell
26 lines
1.0 KiB
Haskell
import qualified Data.Map as M
|
|
|
|
{-
|
|
count function:
|
|
There is stripe which length is n,
|
|
priceMap contains a map for different length of stripe and its price
|
|
then find the maximum price to split the stripe in different shorter stripes
|
|
( including the original length if possible)
|
|
-}
|
|
|
|
priceMap = M.fromList [(1,1),(2,5),(3,8),(4,9),(5,10),(6,17),(7,17),(8,20),(9,24),(10,30)]
|
|
|
|
count n priceMap = _count 1 $M.fromList [(0,0)]
|
|
where
|
|
end = n+1
|
|
_count cur rst
|
|
| cur == end = rst
|
|
| otherwise = _count (1+cur) (M.insert cur price rst)
|
|
where
|
|
newRst = M.insert cur (getValue cur priceMap) rst
|
|
price = maximum. map getPrice $[0..div cur 2]
|
|
getPrice a = (getValue a newRst ) + (getValue (cur-a) newRst)
|
|
getValue key mp
|
|
| M.member key mp = mp M.! key
|
|
| otherwise = 0
|