bzoj 1270 DP

时间:2023-03-10 05:58:27
bzoj 1270 DP

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.