Football--POJ 3071
14863 ワード
1、問題を解く構想:確率論、DP.
2、注意事項:動的繰返し式の各ラウンド、各グループの内部の各チーム間の比較の勝利確率の記録、更新;STL中max_Element()の簡単な応用;pow()はVCとDevCでコンパイルが異なる.
3、実現方法:
2、注意事項:動的繰返し式の各ラウンド、各グループの内部の各チーム間の比較の勝利確率の記録、更新;STL中max_Element()の簡単な応用;pow()はVCとDevCでコンパイルが異なる.
3、実現方法:
#include
<
iostream
>
#include
<
math.h
>
#include
<
algorithm
>
using
namespace
std;
double
flag[
129
],ans[
129
];
double
Arr[
129
][
129
];
int
main()
{
int
n,i,j,k,m;
while
(cin
>>
n
&&
n
!=-
1
)
{
for
(i
=
1
;i
<=
(
int
)pow((
double
)
2
,(
double
)n);i
++
)
{
for
(j
=
1
;j
<=
(
int
)pow((
double
)
2
,(
double
)n);j
++
)
cin
>>
Arr[i][j];
}
for
(i
=
1
;i
<=
(
int
)pow((
double
)
2
,(
double
)n);i
++
)
{
flag[i]
=
1.0
;
ans[i]
=
0.0
;
}
for
(i
=
1
;i
<=
n;i
++
)
{
int
step
=
(
int
)pow((
double
)
2
,(
double
)i);
for
(j
=
1
;j
<=
(
int
)pow((
double
)
2
,(
double
)n);j
+=
step)
{
for
(k
=
j;k
<=
j
+
step
-
1
;k
++
)
{
if
(k
<=
(j
+
step
-
1
)
-
step
/
2
)
{
for
(m
=
(j
+
step
-
1
)
-
step
/
2
+
1
;m
<=
(j
+
step
-
1
);m
++
)
ans[k]
+=
flag[k]
*
flag[m]
*
Arr[k][m];
}
else
{
for
(m
=
j;m
<=
(j
+
step
-
1
)
-
step
/
2
;m
++
)
ans[k]
+=
flag[k]
*
flag[m]
*
Arr[k][m];
}
}
}
for
(j
=
1
;j
<=
(
int
)pow((
double
)
2
,(
double
)n);j
++
)
{
flag[j]
=
ans[j];
ans[j]
=
0.0
;
}
}
int
num
=
1
;
double
tmp
=
0.0
;
num
=
max_element(flag
+
1
,flag
+
(
int
)pow((
double
)
2
,(
double
)n)
+
1
)
-
flag;
cout
<<
num
<<
endl;
}
return
0
;
}