Độ 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';
}