poj 1191
16284 단어 poj
#include
"
stdafx.h
"
#include
<
stdio.h
>
#include
<
math.h
>
#include
<
algorithm
>
using
namespace
std;
int
matrix[
8
][
8
];
int
s[
8
][
8
][
8
][
8
];
int
dp[
15
][
8
][
8
][
8
][
8
];
int
cnt;
double
sum;
double
mmin(
double
a,
double
b)
{
return
a
<
b
?
a : b;
}
int
main()
{
int
x1, x2, y1, y2, k, a;
double
average, sum
=
0
;
scanf(
"
%d
"
,
&
cnt);
for
(x1
=
0
; x1
<
8
; x1
++
)
{
for
(y1
=
0
; y1
<
8
; y1
++
)
{
scanf(
"
%d
"
,
&
matrix[x1][y1]);
sum
+=
matrix[x1][y1];
}
}
average
=
sum
/
cnt;
for
(x1
=
0
; x1
<
8
; x1
++
)
{
for
(y1
=
0
; y1
<
8
; y1
++
)
{
for
(x2
=
x1; x2
<
8
; x2
++
)
{
sum
=
0
;
for
(y2
=
y1; y2
<
8
; y2
++
)
{
sum
+=
matrix[x2][y2];
if
(x2
==
x1)
{
s[x1][y1][x2][y2]
=
sum;
}
else
{
s[x1][y1][x2][y2]
=
s[x1][y1][x2
-
1
][y2]
+
sum;
}
dp[
0
][x1][y1][x2][y2]
=
s[x1][y1][x2][y2]
*
s[x1][y1][x2][y2];
}
}
}
}
int
temp;
for
(k
=
1
; k
<=
cnt
-
1
; k
++
)
{
for
(x1
=
0
; x1
<
8
; x1
++
)
{
for
(y1
=
0
; y1
<
8
; y1
++
)
{
for
(x2
=
x1; x2
<
8
; x2
++
)
{
for
(y2
=
y1; y2
<
8
; y2
++
)
{
dp[k][x1][y1][x2][y2]
=
2000000000
;
for
(a
=
x1; a
<
x2; a
++
)
{
temp
=
mmin(dp[k
-
1
][x1][y1][a][y2]
+
s[a
+
1
][y1][x2][y2]
*
s[a
+
1
][y1][x2][y2],
dp[k
-
1
][a
+
1
][y1][x2][y2]
+
s[x1][y1][a][y2]
*
s[x1][y1][a][y2]);
dp[k][x1][y1][x2][y2]
=
mmin(dp[k][x1][y1][x2][y2], temp);
}
for
(a
=
y1; a
<
y2; a
++
)
{
temp
=
mmin(dp[k
-
1
][x1][y1][x2][a]
+
s[x1][a
+
1
][x2][y2]
*
s[x1][a
+
1
][x2][y2],
dp[k
-
1
][x1][a
+
1
][x2][y2]
+
s[x1][y1][x2][a]
*
s[x1][y1][x2][a]);
dp[k][x1][y1][x2][y2]
=
mmin(dp[k][x1][y1][x2][y2], temp);
}
}
}
}
}
}
double
ret
=
sqrt((
double
)dp[cnt
-
1
][
0
][
0
][
7
][
7
]
/
(
double
)cnt
-
average
*
average);
printf(
"
%.3f
"
, ret);
system(
"
pause
"
);
return
0
;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
POJ3071: Football(확률 DP)Consider a single-elimination football tournament involving 2n teams, denoted 1, 2, …, 2n. After n rounds, only one team...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
