QBSELECT – spoj

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

Tóm tắt đề bài: Cho bảng 4*n, chọn các ô không kề cạnh sao cho tổng các ô chọn lớn nhất

Ví dụ: Xét bảng với n=3 trong hình vẽ dưới đây:

 

Cách chọn cần tìm là tập các ô S = {(3,1), (1,2), (4,2), (3,3)} với trọng lượng 32.

Thuật toán:

–         Theo đề bài thì bảng có 4 dòng và n cột;

• Gọi S là trạng thái chọn các ô ở cột thứ j, ta có thể biểu diễn S bằng 4 bit (các bit được đánh số từ phải sang bắt đầu bằng 0) với ý nghĩa:

+    S[i-1] = 0: dòng thứ i của cột j không được chọn;

+    S[i-1] =1: dòng thứ i của cột j được chọn.

• Với 4 bit, S có thể biểu diễn 16 trạng thái từ {0000} đến {1111} (từ 0 đến 15), tuy nhiên ta nhận thấy chỉ có 8 trạng thái sau là thỏa yêu cầu của bài toán: {0000}, {0001}, {0010},

{0100}, {1000}, {1001}, {0101}, {1010} (tương ứng với các giá trị 0, 1, 2, 4, 5, 8, 9, 10).

• Gọi T[S, j] là trọng lượng lớn nhất khi chọn các ô đến cột thứ j với trạng thái chọn là S, ta có công thức quy hoạch động như sau:

T[S, j] = max(T[P, j-1] + value(S))

với P là trạng thái của cột liền trước của S sao cho P và S không có 2 bit 1 đồng thời ở cùng vị trí, còn value (S) là giá trị cách chọn cột j với trạng thái S.

• Khi cài đặt, với bài toán này, ta chỉ cần xây dựng hàm getBit để giải mã trạng thái S
• Còn thao tác quy hoạch động được thực hiện bình thường

Code:

uses    math;
const   fi='';
        fo='';
        maxn=10000;
        s:array[1..8] of integer = (0,1,2,4,5,8,9,10);
var     t:array[0..maxn,1..8] of longint;
        i,j,k,n:integer;
        res,tam:longint;
        a:array[1..maxn,1..4] of integer;
procedure nhap;
begin
    assign(input,fi);reset(input);

    readln(n);

    for i:=1 to 4 do
        for j:=1 to n do read(a[j,i]);

    close(input);
end;
function getbit(x,y:integer):byte;
begin
    getbit:=(x shr y) and 1;
end;
procedure xuly;
begin
    for i:=1 to n do
        for j:=1 to 8 do
        begin
            tam:=0;
            for k:=1 to 4 do tam:=tam+getbit(s[j],k-1)*a[i,k];
            for k:=1 to 8 do
              if (s[j] and s[k]=0) and (t[i-1,k]+tam>t[i,j])
                then t[i,j]:=t[i-1,k]+tam;
        end;

    res:=low(longint);
    for i:=1 to 8 do res:=max(res,t[n,i]);
end;
procedure inkq;
begin
    assign(output,fo);rewrite(output);

    tam:=low(integer);
    for i:=1 to n do
        for j:=1 to 4 do tam:=max(tam,a[i,j]);

    if tam<=0 then begin writeln(tam); halt; end;

    writeln(res);

    close(output);
end;
begin
    nhap;
    xuly;
    inkq;
end.