SPSEQ – SPOJ

Đề bài: http://vn.spoj.com/problems/SPSEQ/

Thuật toán:

• Gọi f1[i] là độ dài dãy con không giảm dài nhất kết thúc là a[i] của dãy a[1..i]
• Gọi f2[i] là độ dài dãy con không tăng dài nhất bắt đầu là a[i] của dãy a[i..n]
• Kết quả bài toán là:

  2*min(f1[i],f2[i]) -1   với i=1..n;

Code:

uses    math;
const   fi='';
        fo='';
        maxn=trunc(1e5)+3;
        oo=trunc(1e9)+7;
var     a:array[0..maxn] of longint;
        b1,b2:array[0..maxn] of longint;
        f1,f2:array[0..maxn] of longint;
        i,j,n,m,res:longint;
procedure enter;
begin
        assign(input,fi);reset(input);
        readln(n);
        for i:=1 to n do read(a[i]);
        close(input);
end;
function tim1(r,x:longint):longint;
var     d,c,g:longint;
begin
        d:=0;c:=r;
        g:=(d+C) div 2;
        while (g<>d) and (g<>c) do
                begin
                        if b1[g]>=x then c:=g else d:=g;
                        g:=(d+c) div 2;
                end;
        for g:=c downto d do
                begin
                        if b1[g]d) and (g<>c) do
                begin
                        if b2[g]>=x then c:=g else d:=g;
                        g:=(d+c) div 2;
                end;
        for g:=c downto d do
                if b2[g]res1 then
                                begin
                                        inc(res1);
                                        b1[res1]:=a[i];
                                end else
                        if b1[tam1+1]>a[i] then b1[tam1+1]:=a[i];
                        f1[i]:=tam1+1;
                end;
        res2:=1;
        b2[0]:=-oo;
        f2[n]:=1;
        b2[1]:=a[n];
        for i:=n-1 downto 1 do
                begin
                        tam2:=tim2(res2,a[i]);
                        if tam2+1>res2 then
                                begin
                                        inc(res2);
                                        b2[res2]:=a[i];
                                end else
                                if b2[tam2+1]>a[i] then b2[tam2+1]:=a[i];
                        f2[i]:=tam2+1;
                end;
        res:=0;
        for i:=1 to n do
                res:=max( res, 2*min(f1[i],f2[i]) -1 );
end;
procedure print;
begin
        assign(output,fo);rewrite(Output);
        writeln(res);
        close(output);
end;
begin
        enter;
        process;
        print;
end.