TIOJ 1908：大根蘿蔔

TIOJ 1908：大根蘿蔔

題目大意：給 $n\times n$ 的土地，每格有不同價錢的蘿蔔，拔一根周圍八根就不能拔了，問最大獲利。

解法：可以用位元 $dp$，先枚舉所有合法狀態，再找這個狀態全部的合法轉移來源，在 $n=22$ 時總共有 $5592405$ 個，最後再 $dp$ 就好了。

$\text{Code：}$

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;

#define FOR(x,a,b) for(int x=a;x<=b;x++)
#define pb emplace_back

const int SIZE = 5e4;

int n, id[1 << 22], dp[2][1 << 22];
vector<int> mask, last[SIZE];

void dfs (int ori, int now, int i) {
    if (i == n) {
        last[id[ori]].pb (now);
        return;
    }
    dfs (ori, now, i + 1);
    if ( (i == 0 || (now & (1 << (i - 1))) == 0) && (i == 0 || ! (ori & (1 << (i - 1)))) && ! (ori & (1 << i)) && (i == n - 1 || ! (ori & (1 << (i + 1)))))
        dfs (ori, now ^ (1 << i), i + 1);
}

void init() {
    for (int i = 0, I = 1 << n; i < I; i++) {
        if (! (i & (i >> 1))) {
            id[i] = mask.size();
            dfs (i, 0, 0);
            mask.pb (i);
        }
    }
}

void solve() {
    cin >> n;
    init();
    FOR (i, 1, n) {
        int a[n];
        FOR (j, 0, n - 1) cin >> a[j];
        for (int m : mask) {
            int sum = 0;
            FOR (j, 0, n - 1) sum += ( (m & (1 << j)) ? a[j] : 0);
            dp[i & 1][m] = 0;
            for (int l : last[id[m]])
                dp[i & 1][m] = max (dp[i & 1][m], dp[ (i - 1) & 1][l] + sum);
        }
    }
    cout << *max_element (dp[n & 1], dp[n & 1] + (1 << n)) << '\n';
}

int main() {
    ios::sync_with_stdio (false), cin.tie (0);
    solve();
}

我的分享就到這裡結束了，如果喜歡我的 $\text{Blog}$，歡迎追蹤！