# encoding: UTF-8

class Integer
  def to_sub                            # 整数を下付き文字として文字列化
    to_s.tr('0123456789', "₀₁₂₃₄₅₆₇₈₉")
  end
end 

class MutableMatrix                     # Ruby の組み込みの行列クラスは変更不可能
  def initialize (n)
    @size = n                           # 行列大きさは n*n
    @h = {}                             # ハッシュを使って行列をシュミレート
    (0...n).each do |x|
      (0...n).each { |y| @h[[x,y]] = 0 }
    end
  end
  
  def [] (x,y) @h[[x,y]] end
  def []= (x,y,z) @h[[x,y]] = z end
  
  def inspect
    puts
    (0...@size).each do |x|
      (0...@size).each do |y|
        print "#{@h[[x,y]]}, "
      end
      puts
    end
  end
end

class MatrixPlan
  def initialize (dimensions)
    @r = dimensions
    @matrix_count = @r.length-1
    @min_cost = MutableMatrix.new(@matrix_count+1)       # 正方形の行列をゼロで初期化
    @b_best = MutableMatrix.new(@matrix_count+1)         # 分岐点
    optimize
  end
  
  def optimize
    0.upto(@matrix_count-1) { |i| @min_cost[i,i+1] = 0 } # min_cost の初期化
    2.upto(@matrix_count) do |k|
      0.upto(@matrix_count-k) do |a|
        c = a + k
        min_cost = 1/0.0                                 # 無限大
        b_best = 0                                       # ループ外の宣言
        (a+1).upto(c-1) do |b|
          cost = @min_cost[a,b] + @min_cost[b,c] + @r[a]*@r[b]*@r[c]
          min_cost, b_best = cost, b if cost < min_cost
        end
        @min_cost[a,c] = min_cost
        @b_best[a,c] = b_best
      end
    end
  end
  
  def min_cost () @min_cost[0, @matrix_count] end
  def split () @b_best[0, @matrix_count] end
  def solution () solution_part(0, @matrix_count) end
  
  def solution_part(a, c)
    if a >= c-1
      "#{a.to_sub}M#{(a+1).to_sub}"
    else
      b = @b_best[a,c]
      "(#{solution_part(a,b)} * #{solution_part(b,c)})"
    end
  end
end

p =  MatrixPlan.new([100, 2, 200, 3])
puts 'Minimup costs'
puts p.min_cost
puts 'Splits'
puts p.split
puts p.inspect
puts p.solution

p =  MatrixPlan.new([4, 2, 6, 10, 5, 3])
puts 'Minimup costs'
puts p.min_cost
puts 'Splits'
puts p.split
puts p.inspect
puts p.solution

p =  MatrixPlan.new([20, 3, 30, 2, 100])
puts 'Minimup costs'
puts p.min_cost
puts 'Splits'
puts p.split
puts p.inspect
puts p.solution