一种天气情况的概率只与4种天气的出现次数有关，故将相同概率的情况计数后放入堆中模拟哈夫曼树即可。
每次取出概率最小的，将它个数除以2，对于零头需要特判。
#include<cstdio>
#include<queue>
#define N 22
using namespace std;
typedef long long ll;
typedef pair<double,ll>P;
int n,i,j,k,l;ll c[N][N];double A,B,C,D,pa[N],pb[N],pc[N],pd[N],ans;
priority_queue<P,vector<P>,greater<P> >q;
int main(){
scanf("%d%lf%lf%lf%lf",&n,&A,&B,&C,&D);
for(c[0][0]=i=1;i<=n;i++)for(c[i][0]=j=1;j<=i;j++)c[i][j]=c[i-1][j-1]+c[i-1][j];
for(pa[0]=pb[0]=pc[0]=pd[0]=1,i=1;i<=n;i++){
pa[i]=pa[i-1]*A;
pb[i]=pb[i-1]*B;
pc[i]=pc[i-1]*C;
pd[i]=pd[i-1]*D;
}
for(i=0;i<=n;i++)for(j=0;j<=n;j++)for(k=0;k<=n;k++)for(l=0;l<=n;l++)
if(i+j+k+l==n)
q.push(P(pa[i]*pb[j]*pc[k]*pd[l],c[n][i]*c[n-i][j]*c[n-i-j][k]));
while(1){
P t=q.top();q.pop();
if(q.empty()&&t.second==1)break;
if(t.second>1){
if(t.second&1)q.push(P(t.first,1)),t.second--;
ans+=t.first*t.second;
q.push(P(t.first*2,t.second>>1));
}else{
P u=q.top();q.pop();
ans+=t.first+u.first;
q.push(P(t.first+u.first,1));
if(u.second>1)q.push(P(u.first,u.second-1));
}
}
return printf("%.6f",ans),0;
}