从$1$开始依次为一群厨师编号，以参与一项策略厨艺大赛。在轮到某个厨师时，他必须做一道展现自己最好水平的菜，并将其交给一个独立评审团品尝。

第$k$个厨师的水平记作$S(k)$，其值为评委们认为好吃的概率。若一道菜被评委认定为好吃，则该厨师可以将另一名厨师从比赛中剔除，最后剩下的厨师就是胜利者。

比赛从厨师$1$开始，在场上尚未被剔除的厨师中从小到大依次循环（编号最大的厨师完成后再从编号最小的厨师开始）进行。

所有厨师都会根据上述规则最大化自己获胜的概率，同时也会假定其它厨师采取同样的策略。若一位厨师有多个同样好的剔除选择，那么他总是剔除在排在他之后且离他最近的那个。

令$W_n(k)$为厨师$k$在一场共有$n$个厨师参与的比赛中获胜的概率。例如若$S(1)=0.25, S(2)=0.5, S(3)=1$，那么$W_3(1)=0.29375$。

设若$S(k)=F_k/F_{n+1}$，其中$F_k$是以$F_1=F_2=1$为首项的斐波那契数列，那么$n=7$时有 \begin{align*} W_7(1)&=0.08965042, \\ W_7(2)&=0.20775702, \\ W_7(3)&=0.15291406, \\ W_7(4)&=0.14554098, \\ W_7(5)&=0.15905291, \\ W_7(6)&=0.10261412, \\ W_7(7)&=0.14247050, \end{align*} 均保留八位小数。

令$E(n)$为上述假定下有n个厨师参与比赛时预期制作的菜肴总数，例如可以验证$E(7)=42.28176050$。

求$E(14)$，结果保留八位小数。

本题难度:

解答

本题是动态规划问题，但递推关系比较复杂：

用一个14位二进制数m表示当前剩余的厨师，用$E(m,i)$表示在状态m下厨师i作选择时的最优期望菜肴数，$g(m,i)$表示此时的下一位人选，$m'$表示选择后的新状态，则有 $$E(m,i)=1+S(i)E(m',g(m',i))+(1-S(i))E(m,g(m,i)).$$ 再用$W(m,i,j)$表示上述条件下j获胜的概率，则有 $$W(m,i,j)=S(i)W(m',g(m',i),j)+(1-S(i))W(m,g(m,i),j),$$ 每次剔除获胜概率最高的对手，就能依次计算$W,g,E$，最终结果是$729.12106947$。

注：为便于格式化输出和作除法，以下代码为Python 3。

from itertools import product

n=14

F=[1.0, 1.0, 2.0, 3.0, 5.0, 8.0, 13.0, 21.0, 34.0, 55.0, 89.0, 144.0, 233.0, 377.0, 610.0]

for k in range(n+1):
    F[k]/=F[n]

M=1 << n
dp=[[[0.0]*(n|1) for _ in range(n|1)] for _ in range(M|1)]
E=[[0.0]*(n|1) for _ in range(M|1)]

for s in range(1,M):
    chefList=[k for k in range(n) if s & (1 << k)]
    if len(chefList)==1:
        dp[s][chefList[0]][chefList[0]]=1.0
        continue
    order=chefList*3
    for (i,j), k in product(enumerate(chefList), chefList):
        p=E0=E1=0.0
        r=1.0
        for x in range(i,i+len(chefList)):
            opt=order[x]
            optmask=mask=s^(1 << order[x+1])
            optchef=order[x+2]
            optprob=dp[optmask][optchef][opt]
            chef=order[x+1]
            for y in range(x+2, x+len(chefList)):
                mask=s^(1 << order[y])
                if dp[mask][chef][opt]>optprob:
                    optprob,optmask,optchef=dp[mask][chef][opt],mask,chef
            p+=dp[optmask][optchef][k]*r*F[opt]
            if j==k:
                E0+=(x-i+1+E[optmask][optchef])*r*F[opt]
                E1+=len(chefList)*r*F[opt]
            r*=1-F[opt]
        dp[s][j][k]=p/(1-r)
        if j==k:
            E[s][j]=E0/(1-r)+E1*r/(1-r)/(1-r)

print(f"{E[M-1][0]:.8f}")