E. Another Sith Tournament

題目連接：

http://www.codeforces.com/contest/678/problem/E

Description

The rules of Sith Tournament are well known to everyone. n Sith take part in the Tournament. The Tournament starts with the random choice of two Sith who will fight in the first battle. As one of them loses, his place is taken by the next randomly chosen Sith who didn't fight before. Does it need to be said that each battle in the Sith Tournament ends with a death of one of opponents? The Tournament ends when the only Sith remains alive.

Jedi Ivan accidentally appeared in the list of the participants in the Sith Tournament. However, his skills in the Light Side of the Force are so strong so he can influence the choice of participants either who start the Tournament or who take the loser's place after each battle. Of course, he won't miss his chance to take advantage of it. Help him to calculate the probability of his victory.

Input

The first line contains a single integer n (1?≤?n?≤?18) — the number of participants of the Sith Tournament.

Each of the next n lines contains n real numbers, which form a matrix pij (0?≤?pij?≤?1). Each its element pij is the probability that the i-th participant defeats the j-th in a duel.

The elements on the main diagonal pii are equal to zero. For all different i, j the equality pij?+?pji?=?1 holds. All probabilities are given with no more than six decimal places.

Jedi Ivan is the number 1 in the list of the participants.

Output

Output a real number — the probability that Jedi Ivan will stay alive after the Tournament. Absolute or relative error of the answer must not exceed 10?-?6.

Sample Input

3
0.0 0.5 0.8
0.5 0.0 0.4
0.2 0.6 0.0

Sample Output

0.680000000000000

Hint

題意

有n個人在決斗，兩個決斗，然后勝利者繼續決斗

你是0號人物，你可以安排比賽順序，問你最大的獲勝概率是多少

題解：

狀壓dp

你是最后一個上場的人，這個結論猜一下就好了。

然后倒著做。

dp[i][j]表示你還要干死狀態i的人，當前正在打的人是j，然后你獲勝的最大概率是多少

然后直接狀壓dp莽一波就好了。

注意，這個狀態是倒著的。

代碼

#include<bits/stdc++.h> using namespace std; const int maxn = 18; double p[maxn][maxn],dp[1<<maxn][maxn]; int main() {int n;scanf("%d",&n);for(int i=0;i<n;i++)for(int j=0;j<n;j++)cin>>p[i][j];dp[1][0]=1;for(int i=0;i<(1<<n);i++){for(int j=0;j<n;j++)if(i&(1<<j)){for(int k=0;k<n;k++)if(i&(1<<k)&&(k!=j))dp[i][j]=max(dp[i][j],p[j][k]*dp[i^(1<<k)][j]+p[k][j]*dp[i^(1<<j)][k]);}}double ans = 0;for(int i=0;i<n;i++)ans=max(ans,dp[(1<<n)-1][i]);printf("%.12f\n",ans); }

總結

以上是生活随笔為你收集整理的Educational Codeforces Round 13 E. Another Sith Tournament 状压dp的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。