Hướng dẫn giải của Atcoder Educational DP Contest U - Grouping
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Tác giả:
Độ phức tạp thời gian: ~O(3^N + 2^N.N^2)~
Bài này sử dụng quy hoạch động bitmask.
Gọi ~cost[S]~ (với ~S~ là một tập hợp ~N~ phần tử được biểu diễn dưới dạng một bitmask) là tổng số điểm đạt được nếu cho tất cả các chú thỏ thuộc tập ~S~ vào cùng một nhóm. Ta có thể tính được với độ phức tạp thời gian ~O(2^N.N^2)~.
Sau đó, gọi ~dp[S]~ là số điểm tối đa có thể đạt được khi chia nhóm cho các chú thỏ trong tập ~S~. Ta tính ~dp[S]~ bằng cách duyệt qua tất cả các tập con ~T~ của ~S~ và mô phỏng việc cho tất cả chú thỏ thuộc tập con ~T~ vào cùng một nhóm. Ta có thể duyệt tất cả các tập con của tập ~N~ phần tử trong độ phức tạp ~O(3^N)~ (tham khảo bài viết này). Độ phức tạp này vừa đủ với ~N \le 16~.
Để hiểu thêm về cách xử lí bitmask trong code dưới đây, các bạn có thể tham khảo bài viết này.
#include <bits/stdc++.h> using namespace std; int n; const int MAXN = 16; int a[MAXN][MAXN]; long long cost[1 << MAXN]; long long dp[1 << MAXN]; int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n; for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) cin >> a[i][j]; for (int i = 0; i < (1 << n); ++i) for (int j = 0; j < n; ++j) for (int k = j + 1; k < n; ++k) if (i & (1 << j) && i & (1 << k)) cost[i] += a[j][k]; for (int i = 0, j; i < (1 << n); ++i) { j = ((1 << n) - 1) ^ i; for (int k = j; k; k = (k - 1) & j) dp[i ^ k] = max(dp[i ^ k], dp[i] + cost[k]); } cout << dp[(1 << n) - 1] << '\n'; }
Bình luận
Để hiểu thêm về cách xử lí bitmask trong code trên, các bạn có thể tham khảo bài viết sau đây: https://vnoi.info/wiki/translate/topcoder/fun-with-bits.md