Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

QBSELECT - VOI06 Chọn ô

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/qbselect


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.


Được gửi lên bởi:special_one
Ngày:2008-09-25
Thời gian chạy:0.200s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:Vietnam Olympiad of Informatics 2006 - Bảng B

hide comments
2021-11-09 08:40:22
không biết làm
2021-04-12 16:35:52
không chọn gì có phải cách chọn không?
2019-10-24 05:36:09
quay lui full test. nói không với quy hoạch động trạng thái.
#include <bits/stdc++.h>
using namespace std;
int main()
{
#ifndef ONLINE_JUDGE
freopen("qbselect.inp", "r", stdin);
#endif
ios_base::sync_with_stdio(false);
cin.tie(NULL);
long long n;
cin >> n;
vector<vector<long long>> A(4, vector<long long>(n));
for (long long i = 0; i < 4; i++)
for (long long j = 0; j < n; j++)
cin >> A[i][j];
vector<vector<long long>> adjacent(1 << 4);
vector<long long> possible_states;
for (long long u = 0; u < (1 << 4); u++)
{
bool invalid_state = false;
for (long long i = 0; i < 4 - 1; i++)
if ((u & (1 << i)) && (u & (1 << (i + 1))))
{
invalid_state = true;
break;
}
if (invalid_state)
continue;
possible_states.push_back(u);
}
for (auto u : possible_states)
for (auto v : possible_states)
{
bool invalid_state = false;
for (long long i = 0; i < 4; i++)
if ((u & (1 << i)) && (v & (1 << i)))
{
invalid_state = true;
break;
}
if (invalid_state)
continue;
adjacent[u].push_back(v);
}
auto reward = [&](long long state, long long column) {
long long sum = 0;
for (long long i = 0; i < 4; i++)
if (state & (1 << i))
sum += A[i][column];
return sum;
};
vector<vector<long long>> M(n, vector<long long>(1 << 4, -1));
function<long long(long long, long long)> bt = [&](long long i, long long state) {
if (M[i][state] != -1)
return M[i][state];
if (i == n - 1)
return M[i][state] = reward(state, i);
long long maxn = -0x3f3f3f3f3f3f3f3f;
for (auto next : adjacent[state])
maxn = max(maxn, bt(i + 1, next));
return M[i][state] = maxn + reward(state, i);
};
long long maxn = -0x3f3f3f3f3f3f3f3f;
for (auto state : possible_states)
maxn = max(maxn, bt(0, state));
if (maxn == 0)
{
long long adjusted = -0x3f3f3f3f3f3f3f3f;
for (auto row : A)
adjusted = max(adjusted, *max_element(row.begin(), row.end()));
cout << adjusted;
return 0;
}
cout << maxn;
}
2019-09-24 04:59:33
trau cx AC :v
duonght_pro_xinhgainhathemattroi_:)
2019-07-16 03:59:45
ez
2018-08-16 12:41:38
94,12 ??? :D int64_t rồi mà :<
2018-05-29 17:23:46
yeu_laptring_ nhe cac bac :) ,, nho dung kieu long :) thay cho int (QHDTT).
2018-05-15 10:44:25
code mau kem huong dan chi tiet by phan : https://bit.ly/2rGLQbU
2017-12-11 10:29:46
1 đấm AC =))))))
Mới học bitmask
frostpixel aka.How 2 AC
2017-10-04 01:40:29
Code AC: http://123link.top/QBSELECT
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.