| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
有点像线段树?(雾)因为没清空变量wa了两次。。#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int lim = 1 << 8;
double p[lim][lim];
double wins[lim][8]; // wins[i][k] 第i+1队在倒数第k次比赛中存活概率
void dfs(int l, int r, int dep) { // 有点像线段树?
if (l + 1 == r) return (void)(wins[l][dep] = 1);
int mid = (l + r) >> 1;
dfs(l, mid, dep + 1);
dfs(mid, r, dep + 1);
for (int i = l; i < mid; ++i) {
wins[i][dep] = 0;
for (int j = mid; j < r; ++j)
wins[i][dep] += wins[i][dep + 1] * p[i][j] * wins[j][dep + 1];
}
for (int i = mid; i < r; ++i) {
wins[i][dep] = 0;
for (int j = l; j < mid; ++j)
wins[i][dep] += wins[i][dep + 1] * p[i][j] * wins[j][dep + 1];
}
}
int main() {
int n;
while (scanf("%d", &n), ~n) {
for (int i = 0; i < (1 << n); ++i)
for (int j = 0; j < (1 << n); ++j) scanf("%lf", p[i] + j);
dfs(0, (1 << n), 0);
int pos = 0;
for (int i = 1; i < (1 << n); ++i)
if (wins[i][0] > wins[pos][0]) pos = i;
printf("%d\n", pos + 1);
}
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator