题解 P2008 【大朋友的数字】

lyx613 · 2014-01-01 21:47:56 · 题解

看看数据范围n<=10000 n2朴素过不了，但洛谷的神评测机------rn下附n2朴素代码：```delphi rnvar a,f,num:array[0..10000]of longint;rn b,c,d,i,j,k:longint;rnbeginrn read(b);rn for i:=1 to b do read(a[i]);rn for i:=1 to b dorn beginrn f[i]:=1;num[i]:=a[i];rn for j:=1 to i-1 dorn if (a[j]<=a[i])and(f[j]+1>f[i]) thenrn beginrn f[i]:=f[j]+1;rn num[i]:=a[i]+num[j];rn end;rn end;rn for i:=1 to b do write(num[i],' ');rnend.rn直接在dp的同时植入求和运算