題意：

? ? ? ?一共有n個人打擂臺，第一個人是主角，他能任意選擇那兩個人相互比較，贏得成為擂主，繼續和其他人比較，

? ? ? 問，主角想贏的概率最大多大。

題解：

? ? ? ?dp[i][j]代表存活人集合為i的情況下j為擂主，主角獲勝的概率，

? ? ? so ： dp[stat][i]=max(dp[stat][i],a[i][j]*dp[stat^(1<<j)][i]+a[j][i]*dp[stat^(1<<i)][j]);

#include<bits/stdc++.h>#define ll long long using namespace std; const int maxn=20; double a[maxn][maxn]; double dp[1<<20][maxn];//存活人集合為i的情況下j為擂主主角獲勝概率 int main(){int n;scanf("%d",&n);for(int i=0;i<n;++i)for(int j=0;j<n;++j)scanf("%lf",&a[i][j]);dp[1][0]=1;for(int stat=3;stat<(1<<n);stat+=2){for(int i=0;i<n;++i)if(stat&(1<<i)){for(int j=0;j<n;++j)if(j!=i&&(stat&(1<<j))){dp[stat][i]=max(dp[stat][i],a[i][j]*dp[stat^(1<<j)][i]+a[j][i]*dp[stat^(1<<i)][j]);}}}double ans=0;for(int i=0;i<n;++i)ans=max(ans,dp[(1<<n)-1][i]);printf("%.10lf",ans);return 0; }

總結

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

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