【POJ】3071 Football

http://poj.org/problem?id=3071

题意:2^n支队伍进行淘汰赛,每一轮都是第一个与第二个,第三个与第四个比赛,给出了这些人之间的胜率,赢了的进入下一轮,相对位置不变。一共n轮比赛。问哪支队伍n轮比赛后的胜率最大。(n<=7)

#include <cstdio>
using namespace std;
const int N2=(1<<7)+5, N=8;
double d[N2][N], a[N2][N2];
int p[N2][N], n, n2;
int main() {
for(int i=1; i<=128; ++i) p[i][1]=i-1;
for(int i=1; i<=128; ++i) for(int j=2; j<=7; ++j) p[i][j]=p[i][j-1]>>1;
while(scanf("%d", &n), ~n) {
n2=1<<n;
for(int i=1; i<=n2; ++i) for(int j=1; j<=n2; ++j) scanf("%lf", &a[i][j]);
for(int i=1; i<=n2; ++i) d[i][0]=1;
for(int j=1; j<=n; ++j) for(int i=1; i<=n2; ++i) {
int pos=p[i][j]^1;
double sum=0;
for(int k=1; k<=n2; ++k) if(p[k][j]==pos)
sum+=d[k][j-1]*a[i][k];
d[i][j]=d[i][j-1]*sum;
}
int ans; double mx=-1;
for(int i=1; i<=n2; ++i) if(d[i][n]>mx) { mx=d[i][n]; ans=i; }
printf("%d\n", ans);
}
return 0;
}

  

设d[i][j]表示第i个人第j轮比赛的胜率,最后比较d[i][n]就是答案

显然:

d[i][0]=1;

d[i][j]=d[i][j-1]\sum_{k=1}^{T} d[b[k]][j-1]*a[i][b[k]], b[k]表示第j场比赛可能会与i决斗的人的标号

然后乱搞就行了= =

上一篇:『Python CoolBook』数据结构和算法_字典比较&字典和集合


下一篇:从傅里叶变换(FFT)到数论变换(NTT)