#include
<
fstream
>
using
namespace
std;
int
n;
int
a[
101
];
int
f[
101
][
101
];
int
s[
101
][
101
];
int
main()
{
ifstream cin(
"
stone.in
"
);
ofstream cout(
"
stone.out
"
);
cin
>>
n;
for
(
int
i
=
1
;i
<=
n;
++
i)
cin
>>
a[i];
int
MAX
=
0x7FFFFFFF
;
for
(
int
ti
=
1
;ti
<=
n;
++
ti){
if
(ti
!=
1
){
int
tmp
=
a[ti]; a[ti]
=
a[ti
-
1
]; a[ti
-
1
]
=
tmp;
}
memset(f,
0x7F
,
sizeof
(f));
memset(s,
0x7F
,
sizeof
(s));
for
(
int
i
=
1
;i
<=
n;
++
i){
f[i][i]
=
a[i];
s[i][i]
=
0
;
}
for
(
int
k
=
2
;k
<=
n;
++
k)
for
(
int
i
=
1
;i
<=
n
-
k
+
1
;
++
i){
int
j
=
i
+
k
-
1
;
for
(
int
t
=
j
-
1
;t
>=
i;
--
t)
if
(f[i][j]
>
f[i][t]
+
f[t
+
1
][j]){
f[i][j]
=
f[i][t]
+
f[t
+
1
][j];
if
(s[i][j]
>
f[i][j]
+
s[i][t]
+
s[t
+
1
][j])
s[i][j]
=
f[i][j]
+
s[i][t]
+
s[t
+
1
][j];
}
else
if
(f[i][j]
==
f[i][t]
+
f[t
+
1
][j]){
if
(s[i][j]
>
f[i][j]
+
s[i][t]
+
s[t
+
1
][j])
s[i][j]
=
f[i][j]
+
s[i][t]
+
s[t
+
1
][j];
}
}
if
(s[
1
][n]
<
MAX) MAX
=
s[
1
][n];
if
(ti
!=
1
){
int
tmp
=
a[ti]; a[ti]
=
a[ti
-
1
]; a[ti
-
1
]
=
tmp;
}
}
cout
<<
MAX
<<
endl;
return
0
;
}
posted on 2009-05-01 16:53
xfstart07 阅读(151)
评论(0) 编辑 收藏 引用 所属分类:
代码库