- 多边形
- 2009-07-14 17:59:14 @
实型,精确到15位。我用int64的时候也一样 WA了5个点。
请大牛帮忙看一下,我就是一个简单的环DP。
program li;
var n:longint;
i,j,k:longint;
maxn,minn:real;
s:ansistring;
a:array[0..101] of real;
f:array[0..101,0..101] of real;
function max(x,y:real):real;
begin
if x>y then max:=x else max:=y;
end;
function min(x,y:real):real;
begin
if x>y then min:=y else min:=x;
end;
begin
readln(n);
readln(s);
for i:=1 to n do
begin read(a[i]); a:=a[i]; end;
s:=s+s;
for i:=1 to 2*n do f[1,i]:=a[i];
for i:=2 to n do
for j:=1 to n*2-i do
begin
f:=-1000000000;
for k:=1 to i-1 do
begin
if s[j+k-1]='*' then
f:=max(f,f[k,j]*f);
if s[j+k-1]='+' then
f:=max(f,f[k,j]+f);
end;
end;
maxn:=f[n,1];
for i:=2 to n do
if f[n,i]>maxn then maxn:=f[n,i];
writeln(maxn:0:0);
for i:=1 to 2*n do f[1,i]:=a[i];
for i:=2 to n do
for j:=1 to n*2-i do
begin
f:=1000000000;
for k:=1 to i-1 do
begin
if s[j+k-1]='*' then
f:=min(f,f[k,j]*f);
if s[j+k-1]='+' then
f:=min(f,f[k,j]+f);
end;
end;
minn:=f[n,1];
for i:=2 to n do
if f[n,i]
3 条评论
-
小小小学生 LV 9 @ 2009-07-15 17:35:02
我知道发生什么事了
乘法的时候,最大的并不是单纯的 大*大,而最小的也不是单纯的 小*小!
谢谢! -
2009-07-15 17:11:27@
??
DP
不是自动考虑了的吗? -
2009-07-14 19:03:38@
负权没考虑吧
- 1