2022CCPC威海站 D - Sternhalma // 状压dp + 记忆化搜索

题目来源：2022 China Collegiate Programming Contest Weihai Site D - Sternhalma

题目链接：https://codeforces.com/gym/104023/problem/D

题意

在一个\(19\)个格子的六边形棋盘上，每个格子有一个固定的权值 \(w_i\)，格子上可以放置棋子。

可以进行以下两种操作：

• 移除某个格子上的棋子，获得 \(0\) 权值.
• 将一个棋子，以与他相邻的棋子作为跳板，跳到对称位置，跳跃后，作为跳板的棋子被移除，并获得跳板棋子所在格子的权值 \(w_i\).

有 \(t\) 组案例，每组案例给出棋子的放置情况，要求输出最大能获得的权值和。

数据范围：\(-10^6 \le w_i \le 10^6\)，\(1 \le t \le 10^4\).

思路：状压dp + 记忆化搜索

由于格子的数量只有 \(19\) 个，考虑状态压缩，第 \(i\) 位为 \(0/1\) 表示第 \(i\) 个格子 无/有 棋子。

记当前状态为 \(state\)，其第 \(i\) 位为 \(state_i\)，其能获得的最大权值和为 \(f[state]\)，则

• 对于操作一

  若有 \(state_i = 1\)，有转移 \(f[state] = max(f[state], f[state-2^i])\).

• 对于操作二

  若有 \(state_i = 1\)，记格子 \(i\) 做跳板时，跳跃前后的格子为 \(a\)，\(b\)，若有\(state_a = 1\ and\ state_b = 0\)，则有转移 \(f[state] = max(f[state], f[state - 2^i - 2^a + 2^b])\).

为了方便转移，我们可以先将每个格子做跳板时，合法的跳跃前后的格子对，预处理出来。

因为格子的权值固定，因此可以用记忆化搜索。

时间复杂度：\(O(t·n + 2^n)\)，其中 \(n=19\).

代码

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

const int N = 19;

int w[N], f[1 << N], vis[1 << N];
vector<pair<int,int>> v[N];  // v[i]：格子i作为跳板时，合法的跳跃前后格子
 
// 跳板格子，以及跳跃前后的两个格子
void add(int mid, int a, int b) 
{
    v[mid].push_back({a, b});
    v[mid].push_back({b, a});
}

int dfs(int state)
{
    if(vis[state]) return f[state];

    // Remove 
    for(int i = 0; i < N; ++ i) {
        if(!(state >> i & 1)) continue;
        f[state] = max(f[state], dfs(state - (1 << i)));
    }

    // Remove by jumping
    for(int i = 0; i < N; ++ i) {
        if(!(state >> i & 1)) continue;
        for(auto p : v[i]) {
            int a = p.first, b = p.second;
            if(!(state >> a & 1) || (state >> b & 1)) continue;
            f[state] = max(f[state], dfs(state - (1 << i) - (1 << a) + (1 << b)) + w[i]);
        }
    }

    vis[state] = 1;
    return f[state];
}

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

    for(int i = 0; i < N; ++ i) cin >> w[i];
    memset(f, -0x3f, sizeof f);
    f[0] = 0, vis[0] = 1;

    add(1, 0, 2);
    add(3, 0, 7);
    add(4, 0, 9), add(4, 1, 8), add(4, 3, 5);
    add(5, 1, 10), add(5, 2, 9), add(5, 4, 6);
    add(6, 2, 11);
    add(8, 3, 13), add(8, 4, 12), add(8, 7, 9);
    add(9, 4, 14), add(9, 5, 13), add(9, 8, 10);
    add(10, 5, 15), add(10, 6, 14), add(10, 9, 11);
    add(12, 7, 16);
    add(13, 8, 17), add(13, 9, 16), add(13, 12, 14);
    add(14, 9, 18), add(14, 10, 17), add(14, 13, 15);
    add(15, 11, 18);
    add(17, 16, 18);

    int test;
    cin >> test;
    while(test--) {
        string s, t;
        for(int i = 0; i < 5; ++ i) cin >> t, s += t;
        int state = 0;
        for(int i = 0; i < N; ++ i) {
            if(s[i] == '#') state += 1 << i;
        }
        cout << dfs(state) << endl;
    }

    return 0;
}