NKJUMP – spoj

Đề bài: [xem đề bài]

Thuật toán:

• Nhận thấy một vòng bất kỳ chỉ có thể nhảy đến vòng có số lớn hơn. Ta nghĩ đến sử dụng phương pháp Quy hoạch động để giải.
• Ban đầu sắp xếp lại mảng A.
• Gọi F[i] là số bước lớn nhất để nhảy đến ô thứ i.
• F[i] = max(F[j]+1, F[i]) với i=1..n, j=1..i-1 và tồn tại k sao cho a[k]+a[j]=a[i].
• Kiểm tra xem có tồn tại k bằng cách sử dụng tìm kiếm nhị phân

Code:

C++ (xem code trên ideone)

#include 

using namespace std;

const int maxn = 1009;
int i, j, n, a[maxn], b[maxn], f[maxn];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a+1,a+n+1);
    int tmp, ans = 0;
    for (int i = 1; i <= n; i++) f[i] = 1;
    for (int i = 3; i <= n; i++) {
        for (int j = 1; j < i; j++) {
            bool tmp = binary_search(a+1,a+j,a[i] - a[j]);
            if (tmp == 1) {
                f[i] = max(f[i], f[j] + 1);
            }
        }
        ans = max(ans, f[i]);
    }
    cout << ans << endl;
    return 0;
}

Pascal (xem code trên ideone)

uses    math;
const   fi='';
        fo='';
        maxn=1000;
type    arra=array[1..maxn] of longint;
var     f:text;
        a,l:arra;
        i,j,n:integer;
        tmp2:longint;
        res:longint;
procedure nhap;
begin
    assign(f,fi);
    reset(f);
    readln(f,n);
    for i:=1 to n do
    begin
        read(f,a[i]);
    end;
    close(f);
end;
procedure sort;
var     w:longint;
begin
    for i:=1 to n do
        for j:=i+1 to n do
        if a[i]>a[j] then
        begin
            w:=a[i];
            a[i]:=a[j];
            a[j]:=w;
        end;
end;
procedure init;
begin
    res:=0;
    for i:=1 to n do l[i]:=1;
end;
function kt(x,k:longint):boolean;
var     d,c,g,ii:longint;
begin
    d:=1; c:=k;
    kt:=false;
    while d<=c do
    begin
        g:=(d+c) div 2;
        if a[g]=x then begin tmp2:=g; exit(true); end;
        if a[g]max3 then max3:=y;
    if z>max3 then max3:=z;
end;
procedure xuly;
var     tmp:longint;
begin
    for i:=1 to n do
    begin
        tmp:=a[i];
        for j:=i-1 downto 1 do
        begin
            if a[j]>=tmp div 2 then
                begin
                   if kt(tmp-a[j],j-1) then
                        begin
                        l[i]:=max3(l[i],l[j]+1,l[tmp2]+1);
                        if l[i]>res then res:=l[i];
                        end;
                end
            else break;
        end;
    end;
end;
procedure xuat;
begin
    assign(f,fo);
    rewrite(f);
    writeln(f,res);
    close(f);
end;
begin
    nhap;
    sort;
    init;
    xuly;
    xuat;
end.