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à:
    <span class="nu0">2</span>*min<span class="br0">(</span>f1<span class="br0">[</span>i<span class="br0">]</span>,f2<span class="br0">[</span>i<span class="br0">]</span><span class="br0">)</span> -<span class="nu0">1   với i=1..n;</span>

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]<x then exit(g);
                end;
        exit(0);
end;
function tim2(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 b2[g]>=x then c:=g else d:=g;
                        g:=(d+c) div 2;
                end;
        for g:=c downto d do
                if b2[g]<x then exit(g);
        exit(0);
end;
procedure process;
var     tam1,tam2:longint;
        res1,res2:longint;
begin
        res1:=1;
        b1[0]:=-oo;
        b1[1]:=a[1];
        f1[1]:=1;
        for i:=2 to n do
                begin
 
                        tam1:=tim1(res1,a[i]);
                        if tam1+1>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.
Khuyên dùng

 

About Aida Nana

Nghề chính là chém gió, quăng bom và ném lựu đạn.
Nghề phụ là cắt cỏ, chém chuối, cưa cây......

Speak Your Mind

*