棋盘分割
Time Limit:1000MS Memory Limit:10000K
Total Submit:490 Accepted:194
Description
将一个８*８的棋盘进行如下分割：将原棋盘割下一块矩形棋盘并使剩下部分也是矩形，再将剩下的部分继续如此分割，这样割了(n-1)次后，连同最后剩下的矩形棋盘共有n块矩形棋盘。(每次切割都只能沿着棋盘格子的边进行)
原棋盘上每一格有一个分值，一块矩形棋盘的总分为其所含各格分值之和。现在需要把棋盘按上述规则分割成n块矩形棋盘，并使各矩形棋盘总分的均方差最小。
均方差
，其中平均值
，xi为第i块矩形棋盘的总分。
请编程对给出的棋盘及n，求出O'的最小值。
Input
第1行为一个整数n(1 < n < 15)。
第2行至第9行每行为8个小于100的非负整数，表示棋盘上相应格子的分值。每行相邻两数之间用一个空格分隔。
Output
仅一个数，为O'（四舍五入精确到小数点后三位）。
Sample Input
3
1 1 1 1 1 1 1 3
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0
1 1 1 1 1 1 0 3
Sample Output
1.633
Source
Noi 99
#include
<
iostream
>
#include
<
cstdlib
>
#include
<
cmath
>
using
namespace
std;
const
int
INF
=
2000000000
;
int
f[
9
][
9
][
9
][
9
][
15
];
int
s[
9
][
9
][
9
][
9
];
int
d[
9
][
9
];
void
init()
{
int
x1, y1, x2, y2;
int
i, j;
int
sum;
for
(x1
=
1
; x1
<=
8
; x1
++
)
for
(y1
=
1
; y1
<=
8
; y1
++
)
for
(x2
=
x1; x2
<=
8
; x2
++
)
for
(y2
=
y1; y2
<=
8
; y2
++
)
{
sum
=
0
;
for
(i
=
x1; i
<=
x2; i
++
)
for
(j
=
y1; j
<=
y2; j
++
)
sum
+=
d[i][j];
s[x1][y1][x2][y2]
=
sum;
f[x1][y1][x2][y2][
1
]
=
sum
*
sum;
}
}
int
main()
{
int
n;
int
i, j, k;
int
x1, y1, x2, y2;
int
a, b;
int
t, tmp;
double
p
=
0
;
scanf(
"
%d
"
,
&
n);
for
(i
=
1
; i
<=
8
; i
++
)
for
(j
=
1
; j
<=
8
; j
++
)
{
scanf(
"
%d
"
,
&
d[i][j]);
p
+=
d[i][j];
}
p
/=
n;
//
cout << "?? "<< p << endl;
init();
for
(k
=
2
; k
<=
n; k
++
)
{
for
(x1
=
1
; x1
<=
8
; x1
++
)
for
(y1
=
1
; y1
<=
8
; y1
++
)
for
(x2
=
x1; x2
<=
8
; x2
++
)
for
(y2
=
y1; y2
<=
8
; y2
++
)
{
tmp
=
INF;
//
竖切
for
(a
=
x1; a
<
x2; a
++
)
{
t
=
min(f[x1][y1][a][y2][k
-
1
]
+
s[a
+
1
][y1][x2][y2]
*
s[a
+
1
][y1][x2][y2]
, f[a
+
1
][y1][x2][y2][k
-
1
]
+
s[x1][y1][a][y2]
*
s[x1][y1][a][y2]);
if
(tmp
>
t)
tmp
=
t;
}
//
横切
for
(b
=
y1; b
<
y2; b
++
)
{
t
=
min(f[x1][y1][x2][b][k
-
1
]
+
s[x1][b
+
1
][x2][y2]
*
s[x1][b
+
1
][x2][y2]
, f[x1][b
+
1
][x2][y2][k
-
1
]
+
s[x1][y1][x2][b]
*
s[x1][y1][x2][b]);
if
(tmp
>
t)
tmp
=
t;
}
f[x1][y1][x2][y2][k]
=
tmp;
}
}
printf(
"
%.3f\n
"
, sqrt(
double
(f[
1
][
1
][
8
][
8
][n])
/
double
(n)
-
p
*
p));
return
0
;
}
posted on 2006-09-08 22:57
豪 阅读(1296)
评论(0) 编辑 收藏 引用 所属分类:
ACM题目