题解：P10865 [HBCPC2024] Genshin Impact Startup Forbidden III

Rindong · 2024-12-18 18:47:13 · 题解

提供一篇搜索题解。

思路

观察题目发现 1 \le k \le 10 并且 a_i \le 3，那么所有的有鱼的格点状态就只有 4^k 种，可以接受，所以我们可以定义一个 10 维数组来做状态减枝（我也是第一次定义那么多维的数组-_-||）。

然后就是怎么搜索了。我们枚举每个未被取完的有鱼的格子，要取到某个格子的鱼，我们可以有五个位置：上下左右中。枚举到一个格点 p_i 后，我们也把 p_i 的上下左右中减去我们要取的数量即可。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
#define PII pair<int, int>
#define x first
#define y second
#define cur (dp[arr[0]][arr[1]][arr[2]][arr[3]]\
[arr[4]][arr[5]][arr[6]][arr[7]][arr[8]][arr[9]])
int arr[15] = { 0 };
int dp[4][4][4][4][4][4][4][4][4][4] = { 0 };
int n, m, k;
PII pos[15];
int dir[5][2] = {
    { 0, 0 }, { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 }
};
void dfs(int step) {
    if (step >= cur) return;
    cur = step;
    vector<int> brr(k);
    for (int c = 0; c < k; c++)
        if (arr[c]) {
            int cnt = arr[c];
            for (int d = 0; d < 5; d++) {
                int x = pos[c].x + dir[d][0],
                    y = pos[c].y + dir[d][1];
                for (int i = 0; i < 5; i++) {
                    int dx = x + dir[i][0],
                        dy = y + dir[i][1];
                    for (int j = 0; j < k; j++)
                        if (dx == pos[j].x && dy == pos[j].y) {
                            brr[j] = arr[j];
                            arr[j] = max(0, arr[j] - cnt);
                        }
                }
                dfs(step + cnt);
                for (int i = 0; i < 5; i++) {
                    int dx = x + dir[i][0],
                        dy = y + dir[i][1];
                    for (int j = 0; j < k; j++)
                        if (dx == pos[j].x && dy == pos[j].y) arr[j] = brr[j];
                }
            }
        }
}
int main() {
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 0; i < k; i++) {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        pos[i] = { x, y };
        arr[i] = z;
    }
    memset(dp, 0x3f, sizeof dp);
    dfs(0);
    printf("%d", dp[0][0][0][0][0][0][0][0][0][0]);
    return 0;
}