Educational Codeforces Round 13 E

tilian
最开始看错了以为是 可以任意选择两人or选择一人胜出
但题意是 可以选择下一个擂主是谁
考虑dp的话
我们显然需要记录一个state以及当前擂主是谁
转移就是 dp[state][i]=max(dp[state][i],dp[state^{(1<<j)][j]*a[i][j]+dp[state}(1<<i)]*a[j][i])
意义是 我们枚举他后一个交战对手是谁 是他从别人哪里抢夺了擂主 还是守擂成功
但最后我们发现第二维和整个dp无关 可以直接省略

void solve() {
    cin>>n;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>a[i][j];
        }
    }
    dp[1]=1;
    for(int i=0;i<(1<<n);i++){
        for(int j=0;j<n-1;j++){
            if(i>>j&1){
                for(int k=j+1;k<n;k++){
                    if(i>>k&1){
                        dp[i]=max(dp[i],dp[i^(1<<j)]*a[k][j]+
                        dp[i^(1<<k)]*a[j][k]);
                    }
                }
            }
        }
    }
    printf("%.16lf",dp[(1<<n)-1]);
}