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 ...
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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 | 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++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 | #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;
Có thể bạn quan tâm
0
|
