Tóm tắt đề bài

Cuội có ban đầu 4 kỹ năng chiến đấu trong tổng số \(k\) kỹ năng (\(k \le 20\)). Có \(n\) phòng (\(n \le 2 \cdot 10^5\)), mỗi phòng thuộc một trong hai loại:

• Phòng chiến đấu: Chứa một tên tội phạm có kỹ năng \(a\). Cuội đánh bại được tên này nếu một trong 4 kỹ năng hiện tại của Cuội có thể khắc chế kỹ năng \(a\) (dựa trên ma trận khắc chế \(M\) kích thước \(k \times k\)).
• Phòng thư viện: Cuội có thể đổi 1 kỹ năng hiện có lấy 1 kỹ năng mới bất kỳ (hoặc giữ nguyên).

Yêu cầu: Tìm số lượng tội phạm tối đa Cuội có thể đánh bại, biết số phòng thư viện không quá 100.

Phân tích

• Kỹ năng và Ma trận \(M\): Ma trận \(M\) cho biết kỹ năng \(i\) có đánh bại được tội phạm kỹ năng \(j\) hay không. Nếu Cuội sở hữu tập kỹ năng \(S\) (\(|S|=4\)), Cuội đánh bại được tội phạm kỹ năng \(a\) nếu tồn tại \(i \in S\) sao cho \(M[i][a] = 1\).
• Trạng thái kỹ năng: Tại bất kỳ thời điểm nào, Cuội luôn có đúng 4 kỹ năng. Số lượng tập hợp 4 kỹ năng khác nhau từ \(k\) kỹ năng là tổ hợp \(C_k^4\). Với \(k=20\), \(C_{20}^4 = \frac{20 \cdot 19 \cdot 18 \cdot 17}{24} = 4845\). Đây là một con số đủ nhỏ để quản lý trong bảng DP.
• Phòng thư viện: Đây là những vị trí duy nhất Cuội có thể thay đổi tập kỹ năng của mình. Vì chỉ có tối đa 100 thư viện, ta có thể chia các phòng chiến đấu thành tối đa 101 đoạn nằm giữa các thư viện.
• Ràng buộc: \(n\) lớn (\(2 \cdot 10^5\)) nhưng số thư viện \(L\) nhỏ (\(\le 100\)) và \(k\) nhỏ (\(\le 20\)) gợi ý một thuật toán Quy hoạch động dựa trên các đoạn giữa các thư viện và trạng thái là tập kỹ năng.

Hướng giải quyết

1. Tiền xử lý

• Nén các phòng chiến đấu: Chia \(n\) phòng thành \(L+1\) đoạn (với \(L\) là số thư viện). Với mỗi đoạn \(p \in [1, L+1]\) và mỗi kỹ năng \(a \in [1, k]\), gọi \(sum[a][p]\) là số lượng tội phạm có kỹ năng \(a\) xuất hiện trong đoạn thứ \(p\).
• Mặt nạ bit (Mask):
  • Với mỗi kỹ năng \(i\), dùng một bitmask can_beat[i] để lưu các kỹ năng tội phạm mà kỹ năng \(i\) có thể đánh bại.
  • Với một tập kỹ năng \(S\) (biểu diễn bằng mask), mặt nạ các tội phạm bị đánh bại bởi \(S\) là: total_beat_mask = OR của các can_beat[i] với mọi \(i \in S\).
• Mã hóa trạng thái: Sử dụng mảng idx[mask] để ánh xạ mỗi mask có đúng 4 bit 1 sang một số nguyên từ \(0 \dots C_k^4-1\) để tối ưu bộ nhớ cho bảng DP.

2. Quy hoạch động (DP)

Gọi \(dp[p][mask]\) là số tội phạm tối đa đánh bại được từ đoạn thứ \(p\) đến hết, khi bắt đầu đoạn \(p\) với tập kỹ năng mask.

Tại mỗi đoạn \(p\) (trước khi vào thư viện tiếp theo):

1. Tính lợi nhuận hiện tại: Số tội phạm bị đánh bại trong đoạn \(p\) bởi mask là:
   
   \[ gain(mask, p) = \sum_{a=0}^{k-1} \{sum[a][p] \mid \text{kỹ năng } a \text{ bị khắc chế bởi ít nhất 1 kỹ năng trong } mask\} \]
2. Chuyển trạng thái tại thư viện: Sau khi đi hết đoạn \(p\), Cuội gặp một thư viện và có các lựa chọn:
   • Không đổi kỹ năng: Giữ nguyên mask.
   • Đổi 1 kỹ năng: Chọn 1 kỹ năng \(i \in mask\) để bỏ đi và thêm 1 kỹ năng \(j \notin mask\) vào. Trạng thái mới là \(mask'\).

Công thức truy hồi (tính từ cuối về đầu hoặc dùng đệ quy có nhớ):

3. Tối ưu hóa

• Để tính nhanh \(gain(mask, p)\), ta tính trước total_beat_mask cho mỗi tập 4 kỹ năng.
• Số lượng trạng thái: \(101 \times 4845\).
• Số lượng chuyển trạng thái: Từ một mask có 4 bit 1, có \(4 \times (k-4)\) cách đổi 1 kỹ năng. Với \(k=20\), con số này là \(4 \times 16 = 64\).
• Tổng độ phức tạp: \(O(L \cdot C_k^4 \cdot 4 \cdot (k-4))\), xấp xỉ \(101 \cdot 4845 \cdot 64 \approx 3 \cdot 10^7\), hoàn toàn đáp ứng thời gian 1-2s.

Độ phức tạp

• Thời gian: \(O(n + L \cdot C_k^4 \cdot k)\)
• Bộ nhớ: \(O(L \cdot C_k^4 + 2^k)\)

Code tham khảo

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;

#define BIT_CHECK(a,b) (!!((a) & (1ULL << (b))))

const int MAXK = 20;
const int MAXL = 105;
const int MAX_STATES = 5000;

int n, k, L = 0;
int sum[MAXK][MAXL];
int memo[MAXL][MAX_STATES];
int can_beat_mask[MAXK]; // can_beat_mask[i] là mask các tội phạm bị kĩ năng i hạ
int state_to_idx[1 << MAXK];
int idx_to_mask[MAX_STATES];
int beat_by_mask[MAX_STATES]; // mask các tội phạm bị hạ bởi tập kĩ năng idx
int cnt_states = 0;

int solve(int p, int m_idx) {
    if (p > L) return 0;
    if (memo[p][m_idx] != -1) return memo[p][m_idx];

    // Tính số tội phạm bị hạ trong đoạn p
    int current_gain = 0;
    int target_mask = beat_by_mask[m_idx];
    for (int i = 0; i < k; ++i) {
        if (BIT_CHECK(target_mask, i)) {
            current_gain += sum[i][p];
        }
    }

    // Lựa chọn 1: Không đổi kỹ năng tại thư viện tiếp theo
    int res = current_gain + solve(p + 1, m_idx);

    // Lựa chọn 2: Đổi 1 kỹ năng tại thư viện tiếp theo (nếu chưa phải đoạn cuối)
    if (p <= L) {
        int mask = idx_to_mask[m_idx];
        for (int i = 0; i < k; ++i) {
            if (BIT_CHECK(mask, i)) { // Bỏ kĩ năng i
                for (int j = 0; j < k; ++j) {
                    if (!BIT_CHECK(mask, j)) { // Thêm kĩ năng j
                        int next_mask = (mask ^ (1 << i)) ^ (1 << j);
                        res = max(res, current_gain + solve(p + 1, state_to_idx[next_mask]));
                    }
                }
            }
        }
    }

    return memo[p][m_idx] = res;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    memset(memo, -1, sizeof(memo));

    cin >> n >> k;
    int start_mask = 0;
    for (int i = 0; i < 4; ++i) {
        int s; cin >> s; start_mask |= (1 << (s - 1));
    }

    for (int i = 0; i < k; ++i) {
        string row; cin >> row;
        for (int j = 0; j < k; ++j) {
            if (row[j] == '1') can_beat_mask[i] |= (1 << j);
        }
    }

    // Tiền xử lý các trạng thái tổ hợp C(k, 4)
    for (int i = 0; i < (1 << k); ++i) {
        if (__builtin_popcount(i) == 4) {
            idx_to_mask[cnt_states] = i;
            state_to_idx[i] = cnt_states;

            int b_mask = 0;
            for(int bit = 0; bit < k; bit++)
                if(BIT_CHECK(i, bit)) b_mask |= can_beat_mask[bit];
            beat_by_mask[cnt_states] = b_mask;

            cnt_states++;
        }
    }

    // Chia các phòng thành các đoạn ngăn cách bởi thư viện
    int current_segment = 1;
    for (int i = 0; i < n; ++i) {
        int type; cin >> type;
        if (type == 1) {
            int a; cin >> a;
            sum[a - 1][current_segment]++;
        } else {
            current_segment++;
        }
    }
    L = current_segment;

    cout << solve(1, state_to_idx[start_mask]) << endl;

    return 0;
}