本题类似于求最长不下降序列,采用动态规划,从最后一层开始往前推,用A数组保存每层的价值,用B数组保存从每层到最后一层所得的最大价值,如B[5]表示第5层开始,到第N层所得的最大价值。因此其动态方程为:B[i]=A[i]+MAX(与i层下面相连的所有层的价值),最后求出B数组中的最大值。
题目:圣诞树
状态: Accepted
测评机: Xeost[5]
得分: 100分
提交日期: 2010-7-29 19:55:00
有效耗时: 1156毫秒
测试结果1: 通过本测试点|有效耗时172ms
测试结果2: 通过本测试点|有效耗时47ms
测试结果3: 通过本测试点|有效耗时47ms
测试结果4: 通过本测试点|有效耗时46ms
测试结果5: 通过本测试点|有效耗时157ms
测试结果6: 通过本测试点|有效耗时156ms
测试结果7: 通过本测试点|有效耗时47ms
测试结果8: 通过本测试点|有效耗时156ms
测试结果9: 通过本测试点|有效耗时156ms
测试结果10: 通过本测试点|有效耗时172ms
提交代码:
var a,b:array[0..100]of longint;
p:array[0..100,0..100]of 0..1;
i,j,n,max,rq,x:longint;
begin
readln(n);
for i:=1 to n do
begin
read(a[i]);
while not eoln do
begin read(x);p[i,x]:=1;end;
readln;end;
b[n]:=a[n];
rq:=b[n];
for i:=n-1 downto 1do
begin
max:=0;
for j:=i+1 to n do
if (p[i,j]=1)and(b[j]>max) then max:=b[j];
b[i]:=max+a[i];
if b[i]>rq then rq:=b[i];
end;
writeln(rq);
end.