QBSELECT Spoj – VOI06 Chọn ô

Nguồn đề bài: http://vn.spoj.com/problems/QBSELECT/

1. Đề bài QBSELECT Spoj

Cho một bảng hình chữ nhật kích thước 4×n ô vuông. Các dòng được đánh số từ 1 đến 4, từ trên xuống dưới, các cột được đánh số từ 1 đến n từ trái qua phải.

Ô nằm trên giao của dòng i và cột j được gọi là ô (i,j). Trên mỗi ô (i,j) có ghi một số nguyên aij , i =1, 2, 3, 4; j =1, 2, …, n. Một cách chọn ô là việc xác định một tập con khác rỗng S của tập tất cả các ô của bảng sao cho không có hai ô nào trong S có chung cạnh. Các ô trong tập S được gọi là ô được chọn, tổng các số trong các ô được chọn được gọi là trọng lượng của cách chọn. Tìm cách chọn sao cho trọng lượng là 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.

Input

Dòng đầu tiên chứa số nguyên dương n là số cột của bảng.

Cột thứ j trong số n cột tiếp theo chứa 4 số nguyên a1j, a2j, a3j, a4j, hai số liên tiếp cách nhau ít nhất một dấu cách, là 4 số trên cột j của bảng.

Output

Gồm 1 dòng duy nhất là trọng lượng của cách chọn tìm được.

Example

Input:

3

-1 9 3

-4 5 -6

7 8 9

9 7 2

Output:

32

Hạn chế

Trong tất cả các test: n ≤ 10000, |aij| ≤ 30000. Có 50% số lượng test với n ≤ 1000.

2. Gợi ý QBSELECT Spoj

– Các bạn dùng thuật toán Quy Hoạch Động trạng thái:

Gọi F[i,x] là trọng lượng lớn nhất nếu xét từ cột 1 đến cột i và trạng thái của cột i được biểu diễn bằng biến x. Công thức Quy Hoạch Động là:

F[i,x]=Max(F[i-1,x’]+Sum(i,x))

Trong đó:

— x và x’ là trạng thái chọn của hai cột liên tiếp nhau (i và i-1) do đó hai trạng thái phải thỏa mãn điều kiện không có hai ô nào được chọn kề nhau.

— Sum(i,x) là trọng lượng tương ứng với trạng thái chọn x của cột i.

3. Code Tham Khảo QBSELECT Spoj

a. Code Pascal

b. Code C++

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *