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