首页 > 代码库 > Codeforces 678E：Another Sith Tournament 状压DP
Codeforces 678E：Another Sith Tournament 状压DP
odd-even number
题目链接：
http://codeforces.com/problemset/problem/678/E
题意：
有n个人打擂台赛，每两个人间都有相对的胜率，主角可以操控比赛顺序，求主角最后获胜的最大概率。
题解：
设dp[i][j]为状态 i （二进制位代表出场选手） j 号选手第一个上场时主角的最大胜率，dp[1][0]=1.0(场上只有主角一个人主角必胜)。
状态转移方程dp[i][j]=max(dp[i][j],dp[i^(1<<j)][k]*p[k][j]+dp[i^(1<<k)][j]*p[j][k]);
代码
#include<stdio.h>#include<string.h>const int N=18;double dp[1<<N][N],p[N][N];double mmax(double x,double y){ return x>y?x:y;}void solve(){ int n; memset(dp,0,sizeof(dp)); scanf("%d",&n); for(int i=0;i<n;++i) for(int j=0;j<n;++j) scanf("%lf",&p[i][j]); dp[1][0]=1.0; 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))&&j!=k) dp[i][j]=mmax(dp[i][j],dp[i^(1<<j)][k]*p[k][j]+dp[i^(1<<k)][j]*p[j][k]);