Editorial for Xếp bí ngô
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Subtask 1
Áp dụng kĩ thuật backtrack quay lui trong ~O(n!n)~.
Subtask 2
Quy hoạch động bitmask trong ~O(2^n \times n^2)~.
Bản chất bài này chính là bài toán Travelling salesman problem. Vì độ hấp dẫn của từng cặp bí ngô tương tự như trọng số cạnh của đồ thị. Và việc sắp xếp các quả bí ngô giống như việc tìm đường đi qua tất cả các đỉnh, mỗi đỉnh đúng một lần.
Ta gọi ~dp[last][mask]~ là độ hấp dẫn lớn nhất nếu xuất phát ở ~last~ và cần phải đi qua tất cả các đỉnh thuộc tập ~mask~. Công thức quy hoạch động sẽ tương tự như sau:
- ~dp[i][0] = 0~.
- Với mỗi ~i \in mask~, ~dp[last][mask] = max(dp[i][mask \setminus \{i\}] + a[last][i])~.
- Đáp án là ~max(dp[i][\{1,2,3,4,5,...n\} \setminus \{i\}])~ với ~i = 1, 2, 3, ...~
Nhiệm vụ còn lại của chúng ta là tìm cách biểu diễn tập ~mask~ sao cho dễ thao tác và độ phức tạp tối ưu nhất. Trong bài này, ta có thể sử dụng bitmask, tức là dùng một biểu diễn nhị phân để xác định tập hợp. Sau đó ta chuyển biểu diễn nhị phân về dạng thập phân và dùng giá trị đó làm ~mask~. Với giới hạn của đề bài thì ~mask \le 2^{18}~ nên cách làm này là khả thi. Cụ thể hơn về bitmask các bạn có thể xem ở đây.
Code tham khảo
// Created by BJMinhNhut
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define FOR(i, a, b) for(int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, a, b) for(int i = (a), _b = (b); i >= _b; --i)
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define MASK(i) (1ll<<(i))
#define BIT(t, i) (((t)>>(i))&1)
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
typedef pair<int, int> ii;
/***Common Functions***/
template <class T>
bool minimize(T &a, T b) {
if (a > b) {
a = b;
return true;
}
return false;
}
template <class T>
bool maximize(T &a, T b) {
if (a < b) {
a = b;
return true;
}
return false;
}
/***End of Template***/
int n;
const int N = 20;
int a[N][N];
int dp[N][1<<N];
const int INF = 1e9;
void Input() {
cin >> n;
FOR(i, 0, n-1) FOR(j, 0, n-1) cin >> a[i][j];
}
int DP(int last, int mask) {
int &res = dp[last][mask];
if (res > -INF) return res;
if (mask == 0) return res = 0;
res = -INF;
for(int t = mask, i; t > 0; t ^= MASK(i)) {
i = __builtin_ctz(t);
maximize(res, DP(i, mask^MASK(i)) + a[last][i]);
}
return res;
}
void Solve() {
int ans = -INF;
memset(dp, -0x3f, sizeof dp);
int start = 0;
FOR(i, 0, n-1)
maximize(ans, DP(i, (MASK(n)-1)^MASK(i)));
cout << ans;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
Input(), Solve();
return 0;
}
Comments