w[i,j]代表高度j,第i颗树的时候的最大值
那么w[i,j]:=max(w[i,j+1],w[k,j+heigh])+sum[i,j];
但是这样枚举是n^3的,我们发现转移的第二个选择w[k,j+heigh]与当前
第I颗树没有关系,所以记录一个高度为H的时候时的最大值直接O(1)转移就行了
我也不知道咋回事儿,pascal一直RE,一年前能A的代码现在还是RE,然后向管理员
联系了下,他们说数据没有问题,还把数据发过来了,一共5个点,最后一个点的in竟然
30MB。。。,挂接都挂不了。。。
/**************************************************************
Problem:
User: BLADEVIL
Language: Pascal
Result: Runtime_Error
****************************************************************/
//By BLADEVIL
var
n, h, d :longint;
tree :array[..,..] of longint;
w :array[..,..] of longint;
p :array[..] of longint;
i, j :longint;
k :longint;
ans :longint;
function max(a,b:longint):longint;
begin
if a>b then max:=a else max:=b;
end;
begin
readln(n,h,d);
for i:= to n do
begin
read(tree[i,]);
for j:= to tree[i,] do
begin
read(k);
inc(tree[i,k]);
end;
end;
for j:=h downto do
for i:= to n do
begin
w[i,j]:=w[i,j+]+tree[i,j];
if j+d<=h then w[i,j]:=max(w[i,j],p[j+d]+tree[i,j]);
p[j]:=max(p[j],w[i,j]);
end;
ans:=-maxlongint;
for i:= to n do ans:=max(ans,w[i,]);
writeln(ans);
end.