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
const
fi='';
fo='';
var
f:text;
n,j,t:Longint;
i,k:byte;
c:array[0..15,0..15]of 0..1;
a:array[0..4,0..10001]of longint;
l:array[0..10001,0..15]of longint;
function d(x:byte):longint;
begin
d:=0;
if x and 1 = 1 then d:=d+a[1,j];
if x shr 1 and 1 =1 then d:=d+a[2,j];
if x shr 2 and 1 =1 then d:=d+a[3,j];
if x shr 3 and 1 =1 then d:=d+a[4,j];
end;
begin
for i:=0 to 15 do
for j:=i to 15 do
begin
c[i,j]:=((i and 1) and (i shr 1 and 1))
or ((i shr 2 and 1) and (i shr 1 and 1))
or ((i shr 2 and 1) and (i shr 3 and 1))
or ((j and 1) and (j shr 1 and 1))
or ((j shr 2 and 1) and (j shr 1 and 1))
or ((j shr 2 and 1) and (j shr 3 and 1))
or ((i and j) and 1) or ((i and j)shr 1 and 1)
or ((i and j)shr 2 and 1) or ((i and j)shr 3 and 1);
c[j,i]:=c[i,j];
end;
assign(f,fi);
reset(f);
readln(f,n);
t:=-50000;
for i:=1 to 4 do
begin
for j:=1 to n do
begin
read(f,a[i,j]);
if a[i,j]>t then t:=a[i,j];
end;
readln(f);
end;
close(f);
if t<0 then begin assign(f,fo); rewrite(f); writeln(f,t); close(f); halt; end;
j:=1;
for i:=0 to 15 do
if c[i,0]=0 then l[1,i]:=d(i) else l[1,i]:=0;
for j:=2 to n do
for i:=0 to 15 do
if c[i,0]=1 then l[j,i]:=0 else
begin
t:=d(i);
for k:=0 to 15 do
if c[i,k]=0 then if l[j,i]<l[j-1,k]+t then l[j,i]:=l[j-1,k]+t;
end;
assign(f,fo);
rewrite(F);
t:=l[n,0];
for i:=1 to 15 do if l[n,i]>t then t:=l[n,i];
writeln(f,t);
close(f);
end.b. Code C++
#include <stdio.h>
#include <algorithm>
#define ll long long
#define maxN 10001
#define minC -200000000
using namespace std;
int n;
int a[5][maxN], f[16][maxN], fr[9][9];
bool flag = false;
int getbit(int k, int x){
return (x >> (k-1)) & 1;
}
void inp(){
int inmax = minC;
for (int i = 1; i <= 4; i++)
for (int j = 1; j <= n; j++){
scanf("%d", &a[i][j]);
inmax = max(inmax, a[i][j]);
}
if (inmax < 0){
printf("%d", inmax);
flag = true;
}
}
int ok(int x, int y){
int bit[5], elsebit[5];
for (int v = 1; v <= 4; v++) bit[v] = getbit(v, x);
for (int v = 1; v <= 4; v++) elsebit[v] = getbit(v, y);
for (int v = 1; v <= 4; v++)
if ((bit[v] & elsebit[v]) == 1) return 0;
return 1;
}
int value(int x, int y){
int bit[5], sum = 0;
for (int v = 1; v <= 4; v++) bit[v] = getbit(v, x);
for (int v = 1; v <= 4; v++)
if (bit[v] == 1) sum += a[v][y];
return sum;
}
int bitmask(){
int d[] = {0, 1, 2, 4, 5, 8, 9, 10}, res = minC;
for (int i = 0; i <= 8; i++)
for (int j = 0; j <= 8; j++) fr[i][j] = ok(d[i], d[j]);
for (int i = 0; i <= n; i++)
for (int j = 0; j <= 8; j++){
int t = minC;
for (int k = 0; k <= 8; k++)
if (fr[j][k] == 1 && f[k][i-1] > t) t = f[k][i-1];
f[j][i] = t + value(d[j], i);
}
for (int i = 0; i <= 8; i++) res = max(res, f[i][n]);
return res;
}
int main(){
//freopen("SELECT.INP", "r", stdin);
//freopen("SELECT.OUT", "w", stdout);
scanf("%d", &n);
inp();
if (flag) return 0;
printf("%d", bitmask());
return 0;
}
