sωēeτ¨fαrm » 日志 » 能量项链(NOIP2006)
能量项链(NOIP2006)
deadrain 发表于 2007-08-16 23:44:45
用数组f[i,j]表示从第i个珠子到第j个珠子合并为一个珠子后，所释放的最大能量，用k表示断点。
状态转移方程为：f[i,j]:=max{ f[i,k]+f[k,j]+a[i]*a[k]*a[j]}
CODE:
-------------------------------------------
program p1312;
var
a:array[1..100] of longint;
f:array[0..100,0..100] of longint;
i,j,k,t,v,u,n,max:longint;
begin
readln(n);
for i:=0 to n-1 do
read(a[i]);
fillchar(f,sizeof(f),0);
for i:=2 to n do
begin
for j:=0 to n-1 do
begin
k:=(j+i) mod n;
max:=0;
for v:=j+1 to j+i-1 do
begin
u:=v mod n;
t:=a[j]*a[u]*a[k]+f[j,u]+f[u,k];
if t>max then max:=t;
end;
f[j,k]:=max;
end;
end;
max:=0;
for i:=0 to n-1 do
if f[i,i]>max then max:=f[i,i];
writeln(max);
end.
状态转移方程为：f[i,j]:=max{ f[i,k]+f[k,j]+a[i]*a[k]*a[j]}
CODE:
-------------------------------------------
program p1312;
var
a:array[1..100] of longint;
f:array[0..100,0..100] of longint;
i,j,k,t,v,u,n,max:longint;
begin
readln(n);
for i:=0 to n-1 do
read(a[i]);
fillchar(f,sizeof(f),0);
for i:=2 to n do
begin
for j:=0 to n-1 do
begin
k:=(j+i) mod n;
max:=0;
for v:=j+1 to j+i-1 do
begin
u:=v mod n;
t:=a[j]*a[u]*a[k]+f[j,u]+f[u,k];
if t>max then max:=t;
end;
f[j,k]:=max;
end;
end;
max:=0;
for i:=0 to n-1 do
if f[i,i]>max then max:=f[i,i];
writeln(max);
end.
相关日志:
- » NOIP结束了
- » 镇江一游（2）
- » 镇江一游（1）
- » zoj 1002 Fire Net
- » 告别之战
收藏:
QQ书签
del.icio.us
订阅:
Google
抓虾
