jzoj P1027【GDOI2005】电路稳定性

时间:2021-09-05 20:47:46

题目大意:
在一个电路上有n个元件,元件i损坏而断开的概率是Pi(i=1,2….n,0<=pi<=1),请你算出整个电路断路的概率。
对电路的表示:
1.一个元件是最小的电路,A表示元件1,B表示元件2,如此类推。
2.K个电路组成的串联电路表示为:电路1,电路2,……,电路K。
3.K个电路组成的并联电路表示为:(电路1)(电路2)……(电路K)。

题解:
1.把字符串换成实型数组。
对于2个原件x跟y
若为串联电路x,y,则断路概率公式为:x+(1-x)*y
若为并联电路(x)(y),则短路概率公式为:x*y。
(用-1表示 ; )用-2表示; ,用-3表示。
2.每一次先把它没有未知数的串联电路短路概率求出来,并合并数值且压缩数组,然后在把它没有未知数的并联电路短路概率求出来,同上一样合并然后压缩。
3.重复(2)操作,知道数组压缩成只有1个,就是答案。

var
a:array ['A'..'Z'] of real;
b:array [0..10000] of real;
i,j,k,n,m:longint;
s:ansistring;
p,ans:real;
begin
readln(n);
readln(s);
for i:=1 to n do
begin
readln(p);
a[chr(64+i)]:=p;
end;
for i:=1 to length(s) do
case s[i] of
'(' :b[i]:=-1;
')' :b[i]:=-2;
',' :b[i]:=-3;
'A'..'Z':b[i]:=a[s[i]];
end;
n:=length(s);
while n<>1 do
begin
for i:=1 to n do
begin
j:=i;
while (b[j]>0) and (b[j-1]<>-3) and (b[j+1]=-3) and (b[j+2]>0) do
begin
b[j+1]:=0;
b[j+2]:=b[j]+(1-b[j])*b[j+2];
b[j]:=0;
j:=j+2;
end;
end;
m:=0;
for i:=1 to n do
if b[i]<>0 then
begin
inc(m);
b[m]:=b[i];
end;
b[m+1]:=0;
n:=m;
for i:=2 to n do
begin
j:=i;
while (b[j-1]=-1) and (b[j+1]=-2) and (b[j+2]=-1) and (b[j+4]=-2) do
begin
b[j-1]:=0; b[j+1]:=0;
b[j+3]:=b[j]*b[j+3];
b[j]:=0;
j:=j+3;
end;
if (b[j-1]=-1) and (b[j+1]=-2) and ((b[j+2]=-3) or (b[j+2]=-2) or (b[j+2]=0)) then
begin
b[j-1]:=0; b[j+1]:=0;
end;
end;
m:=0;
for i:=1 to n do
if b[i]<>0 then
begin
inc(m);
b[m]:=b[i];
end;
b[m+1]:=0;
n:=m;
end;
writeln(b[1]:0:4);
end.