Đề bài: http://vn.spoj.com/problems/HIREHP/
Thuật toán: Dùng cây IT lưu giá trị tối ưu tại mỗi thời gian. Với bài này khi cập nhập thì cập nhập từ lá lên gốc
Code:
uses math; const fi='hirehp.inp'; fo='hirehp.out'; maxn=5*trunc(1e5); oo=trunc(1e18); var tree : array[1..4*maxn] of int64; idleaf : array[1..maxn] of longint; i,j,n : longint; f : array[1..maxn] of int64; t,p : array[1..maxn] of longint; procedure build(k,l,r : longint); var m : longint; begin if l = r then begin idleaf[l] := k; exit; end; m := (l+r) div 2; build(k*2,l,m); build(k*2+1,m+1,r); end; procedure update(j: longint; x : int64); begin i := idleaf[j]; while i > 0 do begin tree[i] := min(tree[i] , x); i := i div 2; end; end; function get(k,l,r,i,j : longint) : int64; var m : longint; tg1,tg2 : int64; begin if (i>r) or (j<l) then exit(oo); if (i<=l) and (j>=r) then exit(tree[k]); m := (l+r) div 2; tg1 := get(k*2,l,m,i,j); tg2 := get(k*2+1,m+1,r,i,j); get := min(tg1,tg2); end; procedure main; var i : longint; begin // assign(input,fi);reset(input); //assign(output,fo);rewrite(output); read(n); for i := 1 to n do read(t[i] , p[i]); for i := 1 to 4*n do tree[i] := oo; build(1,1,n); update(t[1] , p[1]); f[1] := p[1]; for i := 2 to n do begin f[i] := get(1,1,n,i-1,n) + p[i]; update(t[i] , f[i]); end; writeln(get(1,1,n,n,n)); //close(input);close(output); end; begin main; end. |
Recent Comments