比赛 组合计数1 评测结果 AEEEEEEEEE
题目名称 按位或 最终得分 10
用户昵称 ChenBp 运行时间 1.320 s
代码语言 C++ 内存使用 3.45 MiB
提交时间 2026-02-26 11:54:38
显示代码纯文本
#include <iostream>
#include <queue>
#include <utility>
#include <map>
using namespace std;
double a[25];
struct node{
    int u,c;
    double g;
    bool operator<(const node y) const{
        if(u!=y.u) return u<y.u;
        if(g!=y.g) return g<y.g;
        return c<y.c;
    }
    bool operator>(const node y) const{
        return y<*this;
    }
    bool operator==(const node y) const{
        return u==y.u&&c==y.c&&g==y.g;
    }
    bool operator!=(const node y) const{
        return !(*this==y);
    }
};
int main(){
    freopen("haoi2015_set.in","r",stdin);
    freopen("haoi2015_set.out","w",stdout);
    int n;
    cin>>n;
    n=1<<n;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    priority_queue<node>p;
//    map<node,bool>mp;
    p.push({0,0,1});
    double ans=0;
    while(!p.empty()){
        auto now=p.top();
        p.pop();
        if(now.u==n-1){
            ans+=now.g*now.c;
            continue;
        }
//        cout<<now.u;
        for(int i=0;i<n;i++){
            node x;
            x.u=now.u|i;
            x.c=now.c+1;
            x.g=now.g*a[i];
            if(x.u==now.u) continue;
//            if(mp.count(x)) continue;
//            mp[x]=1;
            p.push(x);
        }
    }
    if(ans<=1e-6) cout<<"INF";
    else cout<<ans;
    return 0;
}