讨论 / 纪念一下,我AC的第100题...
Mine_ysd 2010-07-29 05:02:00
点我顶贴 收藏 删除
很简单的一个DP

本题类似于求最长不下降序列,采用动态规划,从最后一层开始往前推,用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.

查看更多回复
提交回复