传送门 看到这个数据范围就应该想到动归了吧。 f[i][j]表示i到j范围内建树的最小期望代价。 枚举中间点就可以了。
uses math;
var
n,i,j,k:longint;
a:
array [
0..
35]
of extended;
f:
array [
0..
35,
0..
35]
of extended;
p,c:extended;
begin
read(n,p,c);
for i:=
1 to n
do read(a[i]);
for i:=
1 to n
do a[i]:=a[i]+a[i-
1];
for i:=
1 to n
do a[i]:=a[i]/a[n];
for i:=
0 to n+
1 do
for j:=
0 to n+
1 do f[i,j]:=
1000000000;
for i:=
1 to n
do f[i,i]:=p*(a[i]-a[i-
1]);
for i:=
1 to n+
1 do f[i,i-
1]:=
0;
for i:=
2 to n
do
for j:=
1 to n-i+
1 do
for k:=j
to j+i-
1 do
f[j,j+i-
1]:=min(f[j,j+i-
1],f[j,k-
1]+f[k+
1,j+i-
1]+p*(a[j+i-
1]-a[j-
1]));
write(f[
1,n]+c:
0:
3);
end.
转载请注明原文地址: https://ju.6miu.com/read-670070.html
