効率のよい荷物配送法

締め切りが 2016/03/15 10:00 AM なので，その 1 分後に投稿されるようにセット

クリスマスにプレゼントを配るサンタクロース。
配り始めると、すべて配るまで戻れません。
そこで、配るプレゼントをすべて持って出発します。
(帰ってくるときにはすべて配り終えているので、持っているプレゼントはなくなります。)

重たいプレゼントを持ったまま長距離を移動するのは大変ですので、サンタクロースも重たいプレゼントは先に配っていきたいと考えています。
そこで、できるだけサンタクロースの負担が少なくなるような順番を決めることにしました。

今回はこどもたちが用意した靴下の大きさが与えられます。
入れるプレゼントの重さは靴下の大きさと同じです。
（１の靴下には重さ１のプレゼント、2の靴下には重さ2のプレゼント、…）

サンタクロースはすべての靴下のサイズを知っており、靴下のサイズに合ったプレゼントを持って出発します。
訪問する家と家の間の距離は、それぞれの家にある靴下の大きさを掛けた値になっています。
例えば、サイズが2の靴下の家と、サイズが3の靴下の家の間の距離は6(2×3)です。

そして、この距離を移動するときには、「持っているプレゼントの重さ」と「距離」を掛けたエネルギーを消費します。
例えば、持っているプレゼントの重さが5で、家の間の距離が6のときは30(5×6)のエネルギーを消費します。

図のような靴下の家があった場合、

「1」→「2」→「3」→「4」の順にプレゼントを配ると、
9×2　　　※9 ： 1を配ったので2,3,4のプレゼントの重さ　　　2 ： 1と2の距離
＋7×6　　　※7 : 1と2を配ったので3,4のプレゼントの重さ　　　6 : 2と3の距離
＋4×12　　　※1 : 1,2,3を配ったので4のプレゼントの重さ　　　12 : 3と4の距離
＝108
のエネルギーを消費します。

「4」→「3」→「2」→「1」の順にプレゼントを配ると、
6×12　　　※6 ： 4を配ったので1,2,3のプレゼントの重さ　　　12 ： 4と3の距離
＋3×6　　　※3 : 4と3を配ったので1,2のプレゼントの重さ　　　6 : 3と2の距離
＋1×2　　　※1 : 4,3,2を配ったので1のプレゼントの重さ　　　2 : 2と1の距離
＝92
のエネルギーを消費します。

しかし、「4」→「1」→「3」→「2」の順にプレゼントを配ると、
6×4　　　※6 : 4を配ったので1,2,3のプレゼントの重さ　　　4 : 4と1の距離
＋5×3　　　※5 : 4,1を配ったので2,3のプレゼントの重さ　　　3 : 1と3の距離
＋2×6　　　※2 : 4,3,1を配ったので2のプレゼントの重さ　　　6 : 3と2の距離
＝51
のエネルギーで済みます。

【問題】
標準入力から靴下の大きさが与えられます。（1行目にデータ数、2行目以降にそれぞれの家にある靴下の大きさ)
※靴下の大きさは正の整数で与えられ、すべて異なる大きさ、最大11個です。

同じ家には一度しか訪れることができず、必ずすべての家を訪問するとき、
必要なエネルギーが最小になる道順を求め、そのエネルギーを出力するプログラムを作成してください。
※図の場合は、この51というエネルギーが最小ですので、標準出力に51を出力します。

入力例
4
2
3
1
4

出力
51


=====
解答

最初に配るのは一番重いもの，
二番目に配るのは，一番軽いもの，
三番目に配るのは，残ったもので一番重いもの（最初の状態で二番目に重いもの）
四番目に配るのは，残ったもので一番軽いもの（最初の状態で二番目に軽いもの）
ということ（証明略(^_^)_）

ということで，以下のようなプログラムでいずれの例題も1秒以内で計算される。


f = function(x) {
    x = sort(x)
    n = length(x)
    library(e1071)
    if (5 >= n) {
        p = permutations(n)
    } else {
        p = permutations(n-4)
        y = x[-c(n, 1, n-1, 2)]
        p = matrix(y[p], ncol=n-4)
        p = cbind(x[n], x[1], x[n-1], x[2], p)
    }
    min.e = 1e200
    junk = apply(p, 1, function(w) {
        sum(sapply(2:n, function(i) sum(w[i:n])*w[i-1]*w[i]))
        })
    cat(min(junk))
}
system.time(f(c(2, 3, 1, 4))) # 51
system.time(f(1:11)) # 6112
system.time(f(c(20, 16, 14, 12, 9, 8, 5, 4, 3, 2, 1))) # 12004

> system.time(f(c(2, 3, 1, 4))) # 51
51   ユーザ   システム       経過  
     0.016      0.001      0.011
> system.time(f(1:11)) # 6112
6112   ユーザ   システム       経過  
     0.315      0.006      0.313
> system.time(f(c(20, 16, 14, 12, 9, 8, 5, 4, 3, 2, 1))) # 12004
12004   ユーザ   システム       経過  
     0.300      0.003      0.295