Hướng dẫn giải của Xếp bí ngô
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người làm lời giải.
Nộp code mẫu trước khi tự giải được bài tập là một hành vi có thể bị ban.
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;
}
Bình luận