Các bạn nhớ xem lại các thao tác với bit, lấy bit, đảo bit.

## Bài 1: [Bảng nhị phân](https://marisaoj.com/problem/378)
- Công thức DP: $f(i, mask)$, xây đến cột thứ $i$, các giá trị điền vào cột thể hiện bởi $mask$.
- Lưu ý trong $mask$ không được có hai bit nào cạnh nhau:
- Với mỗi $mask$, tìm $mask_2$ nằm ở cột $i-1$, nếu $mask \text{ AND } mask_2=0$, nghĩa là $mask$ có thể nằm cạnh $mask_2$ do không có các bit $1$ kề nhau, cập nhật $f(i-1, mask_2)$ lên $f(i,mask)$
- Đáp án à $\sum{f(m,mask)}$ do hàng $m$ có thể là bất cứ $mask$ nào.

Code:
:::spoiler

#include <iostream>
#include <vector>

const int MOD = 1000000007;

int countValidBoards(int n, int m) {
    std::vector<std::vector<int>> dp(1 << m, std::vector<int>(n + 1));

    // Base case
    dp[0][0] = 1;

    for (int row = 1; row <= n; ++row) {
        for (int mask = 0; mask < (1 << m); ++mask) {
            for (int newMask = 0; newMask < (1 << m); ++newMask) {
                if ((newMask & (newMask << 1)) == 0 && (newMask & mask) == 0) {
                    dp[newMask][row] = (dp[newMask][row] + dp[mask][row - 1]) % MOD;
                }
            }
        }
    }

    int total = 0;
    for (int mask = 0; mask < (1 << m); ++mask) {
        total = (total + dp[mask][n]) % MOD;
    }

    return total;
}

int main() {
    int n, m;
    std::cin >> m >> n;

    int result = countValidBoards(n, m);
    std::cout << result << std::endl;

    return 0;
}

:::

## Bài 2: [Bài toán người bán hàng 2](https://marisaoj.com/problem/215)
- Công thức DP: $f(i, mask)$, hiện tại đang đứng ở vị trí $i$. Các bit $1$ trong $mask$ thể hiện các thành phố đã thăm.
- Đánh số các thành phố từ $0$ đến $n-1$, trạng thái bắt đầu $f(0,1)=0$, ở đây, ta bắt đầu từ thành phố $0$, đánh dấu mask là $...0001_2=1$ là đã thăm.
- Vỉ sao bắt đầu ở $0$, vì đề bài yêu cầu đi thành một chu trình khép kín, nên dù bắt đầu ở đâu thì vẫn phải đi thành một vòng.
- Với mỗi $f(i,mask)$, ta sẽ chọn một thành phố $j$ sao cho bit $j$ trong $mask$ là $0$, nghĩa là chưa được thăm, cập nhật $f(j,mask \text{ OR } 1 \ll j) = min(f(j,mask \text{ OR } 1 \ll j), f(i,mask)+A_{i,j})$.
- Đáp án là $f(x, 2^n-1) + A_{x,0}$ với $x$ là một TP khác $0$, phải quay về $0$ nên cộng thêm $A_{x,0}$.

- Code
:::spoiler

#include <bits/stdc++.h>
using namespace std;

const int maxn = 21, oo = 1e9; int n; int c[21][21]; int dp[(1<<21)][21];

signed main() {
    cin.tie(0); ios_base::sync_with_stdio(false);
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> c[i][j];
        }
    }

    memset(dp, 0x3f, sizeof dp);
    dp[1][0]=0;

    for (int mask = 0; mask < (1 << n); mask++) {
        for (int i = 0; i < n; i++) {
            if (((mask >> i) & 1) == 0) continue;

            for (int j = 0; j < n; j++) {
                if (((mask >> j) & 1) == 1) continue;
                dp[mask | (1 << j)][j] = min(dp[mask | (1 << j)][j],
                                             dp[mask][i] + c[i][j]);
            }
        }
    }

    int res = 1e9;
    for (int i = 1; i < n; i++) {
        res = min(res, dp[(1 << n) - 1][i] + c[i][0]);
    }

    cout << res << '\n';
}

:::

## Bài 4: [Pha thuốc 5](https://marisaoj.com/problem/221)
- Công thức: $f(mask)$ là đã chọn những cây nấm thể hiện trong $mask$, sức mạnh tối đa là bao nhiêu. Base case $f(0)=0$, chưa chọn cây nấm nào nên sức mạnh là $0$.
- Với mỗi $f(mask)$, chọn ra $i$ và $j$ sao cho bit $i$ và $j$ trong mask là $0$, cập nhật $f(mask \text{ OR } 1 \ll i \text{ OR } 1 \ll j) = max(f(mask) + A_{i,j})$. Cho thêm cây nấm thứ $i$ và $j$ tạo thành một lọ thuốc.
- Đáp án là $f(2^{n\times2}-1)$, khi sử dụng hết các cây nấm.
- Code
:::spoiler

#include <bits/stdc++.h>

using namespace std;
#define ll int
#define fi first
#define sc second
const int inf = 1e8;
ll dp[1 << 20][20];
ll n;
ll a[20][20];
void inp() {
    cin >> n;
    for (int i = 0; i < 2 * n; i++) {
        for (int j = 0; j < 2 * n; j++) {
            cin >> a[i][j];
        }
    }
}

ll solve(ll x, ll mask) {
    if (x == n) return 0;
    if (dp[mask][x] != -1) return dp[mask][x];
    ll ans = -inf;

    for (int i = 0; i < 2 * n; i++) {
        if (!(mask & (1 << i))) {
            for (int j = 0; j < i; j++) {
                if (!(mask & (1 << j))) {
                    ans = max(ans, solve(x + 1, mask | (1 << i) | (1 << j)) + a[i][j]);
                }
            }
        }
    }
    return dp[mask][x] = ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    inp();
    
    memset(dp, -1, sizeof dp);
    
    cout << solve(0, 0);

}

:::