#include
<
iostream
>
using
namespace
std;
int
N,M;
int
f[
501
][
501
]
=
{
0
};
int
a[
501
]
=
{
0
};
int
b[
501
]
=
{
0
};
int
main()
{
cin
>>
N
>>
M;
int
x
=
0
;
for
(
int
i
=
1
;i
<=
M;
++
i)
for
(
int
j
=
1
;j
<=
N;
++
j)
f[i][j]
=
0xFFFFFFF
;
for
(
int
i
=
1
;i
<=
N;
++
i){
cin
>>
x;
a[i]
=
a[i
-
1
];
b[i]
=
b[i
-
1
];
if
(x) a[i]
++
;
else
b[i]
++
;
f[
1
][i]
=
a[i]
*
b[i];
}
for
(
int
i
=
2
;i
<=
M;
++
i)
for
(
int
j
=
i;j
<=
N;
++
j){
for
(
int
t
=
i
-
1
;t
<
j;
++
t)
if
(f[i][j]
>
f[i
-
1
][t]
+
(a[j]
-
a[t])
*
(b[j]
-
b[t]))
f[i][j]
=
f[i
-
1
][t]
+
(a[j]
-
a[t])
*
(b[j]
-
b[t]);
}
cout
<<
f[M][N]
<<
endl;
return
0
;
}
posted on 2009-06-04 00:45
xfstart07 阅读(236)
评论(0) 编辑 收藏 引用 所属分类:
代码库